Project Euler: Problem 5

Posted on January 9th 2021 in Algorithms by Pim Debaere.

Project Euler: Problem 5

Ever wondered how to find the smallest multiple of consecutive numbers? The people at Project Euler too. Below the fifth problem and a possible solution.

Smallest multiple

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?
Problem 5

The easiest way is to hard code / calculate this. Leaving aside 1, we take the first three numbers (2, 3 and 4), then we get the following (with N = the smallest number divisible by positive numbers from 2 to k):
k = 2; N = 2
k = 3; N = 2 * 3 = 6
k = 4; N = 2 * 3 * 2 = 12
Note that the last factor with k = 4 is not 4, but 2. This is because one 2 was already included in the product and we would otherwise count the value twice. For the next two values we get
k = 5; N = 2 * 3 * 2 * 5 = 60
k = 6; N = 2 * 3 * 2 * 5 = 60
Again, with k = 6 we can see that factor 6 can be omitted because this is already included as 2 * 3.

If we calculate this in the same way for k = 20, we get
N = 2 * 3 * 2 * 5 * 7 * 2 * 3 * 11 * 13 * 2 * 17 * 19 = 232792560

Job well done!
But wouldn't it be nice to determine this outcome without manually calculating this?

Algorithm

The plan is to loop over all numbers, adding up all factors. Below the algorithm, in JavaScript, worked out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function smallestMultiple(k) {
  var inc = 2;
  var step = 2;
  var ret = 2;

  while (ret <= Number.MAX_SAFE_INTEGER) {
    for (var i = 2; i <= k; i++) {
      // if it isn't divisible, skip to the next number
      if (ret % i !== 0) {
        break;
      }

      // otherwise increase our step to be our next number
      if (i === inc) {
        step = ret;
        inc++;
      }

      // if i is equal to our number, we have found our smallest multiple
      if (i === k) {
        return ret;
      }
    }

    ret += step;
  }
}

console.time('run');
var answer = smallestMultiple(20);
console.timeEnd('run');
console.log('Answer: ' + answer);

// output:
// run: 0.0751953125ms
// Answer: 232792560

Fig. 1 – Project Euler: Problem 5 - an elaboration of the problem in JavaScript.

While writing this piece of code may take a little longer than just calculating ourselves, we can notice that it is a lot faster to execute – only 0.07ms! Now if we want to use this to determine this for, say, k = 40, we just need to adjust the argument. For your information: it takes only 0.27ms.