Project Euler : Problem 5

Problem 5 in Project Euler is this:

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

The answer we are looking for is known as the Lowest Common Multiple(LCM), it is the smallest number which is a multiple of all these numbers.

As always we will first investigate a simpler problem.  We will find the LCM of the numbers 6 and 8.  We start by listing the multiples of the first number until we find a number that is a multiple of the lower number:

6 12 18 24 We stop here because 24 is a multiple of 8, therefore 24 is the LCM of 6 and 8

This is the Delphi code for a function to find the LCM of two numbers a and b:

function TfrmMain.LCM(a, b: int64): int64;
var
  x: int64;
begin
  x := a;
  while x mod b <> 0 do
    inc(x, a);
  result := x;
end;

Line 5 creates a local copy of the variable a (we need to preserve variable a because we will be calculating multiples of it). Line 6 checks whether x is divisible by b by using the Delphi function mod which returns the remainder of dividing x by a. If the remainder is not 0, x is not divisible by b and the next multiple of a is calculated by adding a to x. This loop is repeated until x is a multiple of b, and the value x is returned as the function result at line 8.

To find the LCM of more than two numbers we simply break up the problem into finding the LCM of two numbers at a time. For example to find the LCM of 2, 3 and 4 we first find the LCM of 2 and 3 which is 6.  We then find the LCM of this number (6) with the next number (4) which is 12.  Therefore, the LCM of 2, 3 and 4 is 12.

In the case of our problem above we could solve it by repeating this process 19 times as follows (where the notation LCM(1, 2) means ‘the Lowest Common Multiple of 1 and 2′):

let a = LCM(1, 2)
let b = LCM(b, 3)
let c = LCM(b, 4) and so on until we get to 20

However we could reduce the number of steps because the problem has already told us that the LCM of the numbers from 1 to 10 is 2520. We could start our calculations from the number 11:

let a = LCM(2520, 11)
let b = LCM(a, 12)
let c = LCM(b, 13) and so on until we get to 20

This is the Delphi implementation of this algorithm:

procedure TfrmMain.Problem5;
var
i, runningTotal :integer;
begin
runningTotal := 2520;
  for i := 11 to 20 do
runningTotal := LCM(runningTotal, i);
ShowMessage(IntToStr(runningTotal));
end;

Line 5 initialises thevariable  runningTotal to 2520, which is the LCM of the first 10 numbers. Line 7 then runs in a loop from 11 to 20 calculating the new LCM at each iteration of the loop. This uses the LCM function we wrote earlier. The result is displayed at line 8.

As always, the result is calculated almost instantaneously, certainly within the 1 minute limit of Project Euler.

Tags: , ,

One Response to “Project Euler : Problem 5”

  1. I believe everything said was actually very reasonable.

    But, what about this? what if you were to create a killer title?
    I am not suggesting your content is not solid., however what if you added a post title to maybe get folk’s attention?

    I mean Project Euler : Problem 5 ? nimLog is kinda vanilla.
    You might peek at Yahoo’s front page and watch how they create article headlines to grab viewers interested.
    You might try adding a video or a pic or two to get
    people excited about what you’ve got to say. In my opinion, it might make your blog a little bit more interesting.