Project Euler Problem 5 Solution: Smallest multiple

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

Finding the Least Common Multiple (LCM) Using Euclid’s GCD Algorithm

The smallest positive number divisible by each member of a set of integers is known as the Least Common Multiple (LCM). To solve this problem for integers {1, 2, 3, ..., 20}, we can use Euclid’s algorithm to compute the LCM efficiently.

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.

In general, removing smaller factors of larger numbers does not change the LCM. For example, LCM(12, 10, 15, 75) equals LCM(12, 10, 75), as 15 is a factor of 75, making it redundant. This reduction in the number of factors significantly speeds up the computation.

When finding the LCM of a consecutive sequence of integers starting from 1, the bottom half can always be removed as they are factors of the top half.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 5

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

Python Source Code

import math, functools
LCM = lambda a, b: a // math.gcd(a, b) * b
N = int(input("The LCM for numbers 1 through "))
print ("is", functools.reduce(LCM, range(N//2+1, N+1)))

Last Word

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