Project Euler: Problem 1

Posted on July 25th 2020 in Algorithms by Pim Debaere.

Project Euler: Problem 1

Since algorithmic thinking always comes in handy during programming, I occasionally enjoy solving algorithmic problems. A good example of a collection of problems is Project Euler. Every now and then I will post a problem that I have worked out in my own way on this blog. If you want to solve it yourself, don't read these posts – SPOILERS!

Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
Problem 1

There are different wasy to tackle this problem. The first one is a manual sum of the multiples: 3 + 5 + 6 + 9 + 10 + 12 + 15 + … But that quickly gets boring. So we're moving to a different approach, which is to let the computer do the work.

Again, there are multiple options, the simplest of which is to iterate over all numbers less than 1000 and check if this is a multiple of 3 and/or 5. If this is the case, we take this into account to determine the sum. In JavaScript this will look like below. Note that I added code to time the execution time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function sumDivisible(max) {
  var sum = 0;

  // loop through all numbers below n
  for (var i = 1; i <= max; i++) {
    // check if number is divisible by 3 or 5
    if (i % 3 === 0 || i % 5 === 0) {
      sum += i;
    }
  }

  return sum;
}

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

// output:
// run: 0.27880859375ms
// Answer: 233168

Fig. 1 – Project Euler: Problem 1 - looping through all numbers in JavaScript.

This certainly gives the right result and, for this problem at least, in a short time. But suppose the problem was slightly bigger, for example for numbers less than 100,000. Then the execution time comes is 4ms – or 14 times slower. If we go even further, it takes just under 3 seconds (2,983ms) for 1,000,000,000 or even 95 seconds for 10,000,000,000.

That should be more efficient, so let's take a different approach. In fact we can fill this problem in the sum of numbers divisible by 3 plus the sum of numbers divisible by 5. However, we also have a lot of overlap: for example, 15 is divisible by both and will therefore be counted twice and so we have to still subtract the sum of numbers by 15.

Written out this makes:
3 + 6 + 9 + … + 999 5 + 10 + 15 + … + 995 -(15 + 30 + 45 + … + 990)

Or written differently:
3 * (1 + 2 + 3 + … + 333) 5 * (1 + 2 + 3 + … + 199) -(1 + 2 + 3 + … + 66)

Note that 199 equals 995 / 5, but also equals the integer part 999 / 5. The same is true for 66 which is equal to the integer part of 999 / 15. So we can rewrite the above lines to
1 + 2 + 3 + … + p, with p as the integer part of the division 999 / n;
or, using the definition of a triangular number we can rewrite it to
p(p + 1) / 2

We now become the following function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function sumDivisible(n) {
  // ~~() keeps integer part of division
  var p = ~~(max / n);

  return ~~(n * (p * (p + 1) / 2));
}

console.time('run');
var max = 999;
var answer = sumDivisible(max, 3) + sumDivisible(max, 5) - sumDivisible(max, 15);
console.timeEnd('run');
console.log('Answer: ' + answer);

// output:
// run: 0.031982421875ms
// Answer: 233168

Fig. 2 – Project Euler: Problem 1 - a more efficient way in JavaScript.

Conclusion: this way is almost nine times faster when we do this, as requested, for numbers smaller than 1000. The nice thing about this is that it is just three, for a computer, very simple equations and that the execution time will almost always be the same. Whether we run this with limit 10, 1000 or 10,000,000,000.