Find smallest multiple of specific set of numbers

Question

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$.

Answer 1

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.$$

Answer 2

Think of the prime factorization of all the numbers. For each prime, you need as many factors of that prime as the maximum in your set. Example: $LCM(720,81,225)=LCM(2^43^25,3^4,3^25^2)=2^43^45^2=32400$

In your case, you need $2^4$ (from $16$), $3^2$ (from $9$), and single powers of all other primes.

Answer 3

The following is under the assumption the list is of the form $[1,2,3,...,n]$.

If you are looking for an algorithm, then this works

1. Take all the primes in the list.
2. For all the primes, $p_i$, find the largest $m_i$ such that $p_{i}^{m_i} \leq n$.
3. Multiply all these powers of primes together.

For example, given $[1,2,3,...,20]$, you have

$p_1 = 2$ and $m_1 = 4$, $p_2 = 3$ and $m_2 = 2$ and all other $m_i = 1$

which tells you that $\text{lcm}(1,2,3,...,20) = 2^4 \times 3^2 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19$.