Project Euler Problem 5 Statement

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 number that is evenly divisible by all of the numbers from 1 to 20?

Solution

Solving with Euclid’s GCD algorithm

The smallest positive number that is evenly divided (divided without remainder) by a set of numbers is called the Least Common Multiple (LCM). All we have to do to solve this problem is find the LCM for the integers {1, 2, 3, 4, …, 20} using Euclid’s GCD algorithm.

After some reflection you might correctly realize that every integer is divisible by 1, so 1 can be removed from the list and use 2 through 20 instead.

But wait, by furthering this reasoning, we can eliminate other factors as well. We leave 20 in the calculation but then remove its factors {2, 4, 5, 10}. Any number evenly divisible by 20 is also evenly divisible by these factors. 19 is prime and has no factors — it stays. 18 has factors {2, 3, 6, 9} and we already removed 2 but we can remove 3, 6, and 9. 17 is prime — it stays, too.

We continue this numeric carnage until our original list of {1…20} becomes the much smaller {11…20}. In general, all smaller factors of a bigger number in the list can be safely removed without changing the LCM, e.g., LCM(12,10,15,75) = LCM(12,10,75) = 300, as 15 is a factor of 75.

This reduces the number of factors to consider and helps to speed things up.

HackerRank version

Extended to solve all test cases for Project Euler Problem 5

HackerRank requires us to run 10 test cases for 1 ≤ N ≤ 40. No changes to the algorithm are required.

Python Source Code

 Use this link to download the Project Euler Problem 5: Smallest multiple Python source.

 Run Project Euler Problem 5 using Python on repl.it

Last Word

• When finding the LCM of any consecutive sequence of integers, the bottom half can always be removed as they are factors of the top half.
• More reading and some applications for the LCM.
• Python’s reduce(function, sequence [, initial value]) returns a single value constructed by calling the function LCM() on all the items in the sequence. Here’s the equivalent code without using reduce().

q = LCM(11,12)
for n in range(13,21):
    q = LCM(q,n)
print q