// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (24 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 5 Solution

Project Euler 5 Solution

Project Euler 5: Find the smallest number divisible by each of the numbers 1 to 20


Project Euler 5 Problem Description

Project Euler 5: 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?

Project Euler 5 Analysis

Euclid’s 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 is find the LCM for the integers {1, 2, 3, 4, …, 20} using Euclid’s algorithm.

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

But by furthering this reasoning and we can eliminate other factors. 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, 12, 13, 14, 15, 16, 17, 18, 19, 20}. Following this reasoning, the lower half of the set is completely irrelevant and can be eliminated from consideration without changing the result.

from fractions import gcd
def lcm(a, b): 
    return a // gcd(a, b) * b

L = 20
print 'LCM of all numbers from 1 through', L, 'is', reduce(lcm, range(L//2+1, L+1))

A better method for this problem

For larger ranges, say greater than 105, this method becomes very slow. The method outlined below can adeptly handle larger sets such as {2, 3, 4, …, 106}.

Taking 20 as our example, we know the LCM must be divisible by every prime less than or equal to 20. In this case those primes are {2, 3, 5, 7, 11, 13, 17, 19}. For the primes less than square root of 20 there may be an exponent involved, and for those greater than the square root of 20 the exponent will always be 1. Let’s look at the breakdown:

Number

Prime Factors

Number

Prime Factors
11

11

16

24
12

22×3

17

17
13

13

18

2×32
14

2×7

19

19
15

2×5

20

22×5
Now, using the greatest exponent of each prime, multiply them together as:
24 × 32 × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560.
We use the log function to determine the exponent of the prime, p, as log(20)/log(p) by looping through the primes.

For example, the floor of (log 20 / log 2) = 4; the largest exponent of 2 in the prime factors (24 = 16). Again, the floor of (log 20 / log 3) = 2; the largest exponent of 3 in the prime factors (2×32=18).

The HackerRank version ups the limit for 1 ≤ n ≤ 40 and runs test cases up to 10 consecutive trials. This algorithm handles those test cases in less than a hundredth of a second.

Project Euler 5
This program and method
solves all test cases for
Project Euler 5 on HackerRank

Project Euler 5 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 5 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|232792560|

Afterthoughts

  • Notes on Python usage:
    The statement: from Euler import prime_sieve includes a function for calculating prime numbers from our Euler.py library module into the program. Many useful functions can be imported this way without copying its definition into each program. When an improvement is made or an error corrected it only has to be done once and is reflected in the scripts that import it. This keeps scripts short and concise. Function prime_sieve is listed in Common Functions and Routines for Project Euler.

  • In the GCD version we changed return a * b / gcd(a,b) to return a / gcd(a,b) * b. “Because gcd(a, b) is a divisor of both a and b, it’s more efficient to compute the LCM by dividing before multiplying. This reduces the size of one input for both the division and the multiplication, and reduces the required storage needed for intermediate results (overflow in the a×b computation).” [from Wikipedia]

  • Python’s reduce(function, sequence, initial value) returns a single value constructed by calling the binary function mul on the first two items of the sequence, then on the result and the next item and so on.

  • The code shown below removes the use of reduce to achieve the same results.
a = 1
for p in primes:
    a*= p**int(log(L)/log(p))

Project Euler 5

Project Euler 5 Solution last updated

Discussion

2 Responses to “Project Euler 5 Solution”

  1. Hi Mike,

    I once calculated the smallest number divisible by every number between 1 and 100. I posted this on my facebook profile back in 2009.

    69,720,375,229,712,477,164,53​3,808,935,312,303,556,800 is the smallest number divisable by every number from 1 to 100. I calculated this on 4-3-2003.

    Scott

    Posted by Scott Murphy | July 16, 2011, 4:32 PM
    • I ran this program to 100 and confirmed your result. For 1 to 1000 it is:
      7128865274665093053166384155714272920668358861885893040452001991154324087
      5811114994764441519138715869117178170195752565129802640676210092514658710
      0430513107268626814320019660997486274593718834370501543445252373974529896
      3145674982128236956232823794011068809262317708861979540791247754558049326
      4757378299233527517967352480424636380511370343312147817468508784534856780
      21888075373249921995672056932029099390891687487672697950931603520000

      I won’t bother putting in the commas.

      Posted by Mike | July 18, 2011, 1:17 AM

Post a comment