Robert Eisele
Engineer, Systems Architect and DBA

# Project Euler 1: Multiples of 3 and 5

Problem 1

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.

## Solution

The sum of the multiples of 3 or 5 can be calculated quite simple by looping from 1 to 999 and check what numbers are divisible by 3 and 5:

function solution(n) {
var c = 0;
for (var i=1; i < n; i++) {
if (0 === i % 3 || 0 === i % 5)
c+= i;
}
return c;
}


Scanning through a small range like this is no problem for a computer. But a linear complexity for this problem isn't satisfying. Carl Friedrich Gauß re-discovered the famous formula as a child, which is known as the Gauss summation formula:

$\sum\limits_{i=1}^n i = \frac{1}{2}n(n+1)$

We can use this formulation to get to know what the sum of all multiples of 3 or 5 is. All multiples of 3 for example are $$3, 6, 9, 12, ...$$ If we place 3 outside the brackets, it reads $$3\cdot (1, 2, 3, 4, ...)$$. And how many numbers do we need to sum? Of course $$\lfloor\frac{n}{3}\rfloor$$. When we say, we want to find it for a general $$k$$ instead of 3, and calculate the sum of the multiples, we arive at:

$\sigma(n, k) = k\sum\limits_{i=1}^{\lfloor n/k\rfloor} i = k\frac{1}{2}\lfloor n/k\rfloor(\lfloor n/k\rfloor+1)$

If we now sum $$\sigma(999, 3) + \sigma(999, 5)$$, we have one problem: all numbers which are divisible by 3 and 5 are counted twice. As the $$lcm(5,3)=15$$, we have to subtract all multiples of 15, so we finally get: $$\sigma(999, 3) + \sigma(999, 5) - \sigma(999, 15)$$. Implementing it in JavaScript can then look like this:

function solution(n) {

var r = Math.floor(n / 3);
var s = Math.floor(n / 5);
var t = Math.floor(n / 15);

return 0.5 * (
3 * r * (r + 1)
+  5 * s * (s + 1)
- 15 * t * (t + 1));
}

Or minimized/obfuscated a bit more:

function solution(n) {

var r = n / 3 | 0;
var s = n / 5 | 0;
var t = n / 15 | 0;

return 3 * r * ++r + 5 * s * ++s - 15 * t * ++t >> 1;
}
solution(999);


Go to overview