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)

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

Upon reflection, you'll realize that every number is divisible by 1, so 1 can be excluded.

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 decimation and are left with {11, 12, 13, … 20}.

In general, for a sequence of consecutive integers, the lower half can be removed as they are factors of the upper half. This reduction minimizes unnecessary calculations while preserving the result.

In general, when computing the LCM of a sequence of integers, smaller factors of larger numbers are redundant and can be excluded. For instance, the LCM of {12, 10, 15, 75} is the same as the LCM of {12, 10, 75}, since 15 is a factor of 75.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 5

HackerRank Project Euler 5 requires us to run 10 test cases for 1 ≤ N ≤ 40.

Python Source Code

import math, functools

for _ in range(int(input())):
    N = int(input())
    print(functools.reduce(math.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().

import math
LCM = lambda a, b: a // math.gcd(a, b) * b
q = LCM(11,12)
for n in range(13,21):
    q = LCM(q,n)
print(q)