What is the smallest positive number that is evenly divisible by each of the integers from 1 to 24 inclusive?
Clearly all of the primes between 1 and 24 will need to be factors of this number, so let's start with:
2*3*5*7*11*13*17*19*23 = 223092870
Now we just need to check the composite numbers between 1 and 24 to see if they can be formed by multiplying any combination of these primes. If not, we need to add the smallest factor that will make this possible:
4  no (add a second 2 as a factor)
6  yes (2*3)
8  no (add a third 2 as a factor)
9  no (add a second 3 as a factor)
10  yes (2*5)
12  yes (2*2*3)
14  yes (2*7)
15  yes (3*5)
16  no (add a fourth 2 as a factor)
18  yes (2*3*3)
20  yes (2*2*5)
21  yes (3*7)
22  yes (2*11)
24  yes (2*2*2*3)
So our final number is 2*2*2*2*3*3*5*7*11*13*17*19*23, or 223092870*24 = 5354228880.
At this point it also becomes fairly easy to keep going, and find the smallest number evenly divisible by all integers between 1 and 25, 1 and 26, etc.:
(125, 126): 5354228880*5 = 26771144400
(127, 128) = 2677114440*3 = 8031343320
(129, 130) = 8031343320*29 = 2329089562800
(131, 132, 133, 134, 135, 136) = 2329089562800*31 = 72201776446800
In general, moving forward, our number requires a new factor only when we wish to make it divisible by a new prime or a prime raised to a power greater than 1.
Edited on November 11, 2010, 11:55 am

Posted by Jyqm
on 20101111 11:43:45 