2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Programming is allowed.
Bounty: 1000 sats to first correct answer with documented reasoning / code.
Source: Project Euler
1,000 sats paid
232,792,560?
2520 is divisible by 1..10, but not 11.
To make a number divisible by the numbers 11 to 20 in addition to 2520, it needs to be additionally divisible by the primes between 11..20, which are 11, 13, 17 and 19, and by 16 (2^4), because 2520 is already divisible by 12
(2^2*3), 14(2*7), 15(3*5), 16/2=8 (so one "2" is missing in the factorization), 18(2*3^2)and 20(2^2*5).So the result is 2520 * 11 * 13 * 2 * 17 * 19 = 232,792,560
Or to spell it out as a factorization:
2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19
BTW interesting synchronicity - I saw the number 2520 earlier today in this article: https://medium.com/@syndyne.invents/from-structure-to-meaning-8700317ef6dd
Good job, very elegant and I like how you didn't use code.
If I were to use code, I'd do it like this:
result = 2520;for (i = 11; i <= 20; i++) {if (result % i != 0)result *= i / gcd(result, i);}where
gcdis the greatest common divisor.After this,
resultcontains the number.For an arbitrary range from 1..n, the complexity is O(n log n), if
gcduses the standard Euclidean algorithm.nice solve, thank you for sharing
232792560
ah, too late, congrats :)
We can test all numbers until we find one that is divisible by every number from one to twenty. Brute force method.
number = 1
found = false
while ( not found )
--found = true
--for ( i = 1 until i = 20 )
----if ( number / i diff 0 )
------found = false
------stop
I don't think works. as written it will stop on i = 2 with found = false and number = 1
The stop only breaks the for loop, the while loop keeps going. No?
then i think it'll run forever because number does not iterate
lmao. This is an algorithm, it isn't written in any programming language.
I can't code, but Gemini turned my algorithm into Python for me. Ahah
number = 1
found = False
while not found:
found = True
for i in range(1, 21):
if number % i != 0:
found = False
break
if not found:
number += 1
print(f"n = {number}")
2520 no reminder with 7 wow 360 even!!
I would assume a simple loop function that stops with the % is zero should get you to the answer
Let's check this solution with 2520 number
Primes: 1, 2, 3, 5, 7
2^3=8
3^2=9
5^1=5
7^1=7
8 * 9 * 5 * 7=2520
it works
p.s. no need bounty, because I got smarter after your puzzle. It's more expensive
Seventy-twelve
10
Gemini threw up long text and said: 232,792,560