Project Euler Problem 5

Solution

We seek the smallest positive integer divisible by every number from 1 to 20, i.e. the least common multiple (LCM) of the integers $1,2,\dots,20$.

The most efficient mathematical approach is to take the highest powers of all primes ≤ 20:

$2^4 = 16$ (highest power of 2 ≤ 20)
$3^2 = 9$
$5^1 = 5$
$7^1 = 7$
$11,13,17,19$

So:

$$\text{LCM}(1,\dots,20) = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$$

Multiplying:

$$16 \cdot 9 = 144$$

$$144 \cdot 5 = 720$$

$$720 \cdot 7 = 5040$$

$$5040 \cdot 11 = 55440$$

$$55440 \cdot 13 = 720720$$

$$720720 \cdot 17 = 12252240$$

$$12252240 \cdot 19 = 232792560$$

Python code:

import math
from functools import reduce

answer = reduce(math.lcm, range(1, 21))
print(answer)

Mental verification:

The number contains factors needed for divisibility by:
$16$ via $2^4$
$9$ via $3^2$
$5, 7, 11, 13, 17, 19$
Therefore it is divisible by every integer from 1 to 20.
Removing any prime factor would break divisibility for at least one number, so it is minimal.

Answer: 232792560