Find smallest multiple of specific set of numbers I was trying to solve the 5th problem on project-euler.net, wich is finding the smallest number wich was multiple of each number in a specific set, in this case, $[1 ... 20]$. First I thought of was $20!$, wich of course isn't the smallest multiple, but it's a start (made on ruby): set = (1..20).to_a set.reduce(:*) # i.e. 20! => 2_432_902_008_176_640_000 Better kick out the the numbers that already have a multiple in the set: set2 = set.reject do |n| (set-[n]).any? { |i| (i%n).zero? } end => [11, 12, 13, 14, 15, 16, 17, 18, 19, 20] set2.reduce(:*) # 11 * 12 * ... * 20 => 670_442_572_800 # Bingo! ... nope set2.reduce(:*) / 20 / 18 / 2 / 4 # Brute force!! => 232_792_560 # Success What's the logic in this development? I fail to find a pattern between the set $[1 ... 20]$ and the numbers $20$, $18$, $2$ and $4$.

What you want is the least common multiple of $1$ through $20$. This can be computed recursively as: $$\mathrm{lcm}(1,2,\ldots,20)=\mathrm{lcm}(\mathrm{lcm}(1,2),3,\ldots,20)=\cdots$$ or can also be computed by factoring all the numbers $1$ through $20$ to find the highest degree on each prime from $1$ to $20$ in any factor. The primes between $1$ and $20$ are $2,3,5,7,11,13,17,19$. The highest exponent on $2$ in any prime factorization of a number between $1$ and $20$ is $4$, as $2^4=16$ but $2^5=32>20$. For $3$ it is $2$, and for all higher primes it is $1$. Thus we have $$\mathrm{lcm}(1,2,\ldots,20)=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19.$$