Project Euler 1 Solution: 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 \(\left\lfloor\frac{n}{3}\right\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}^{\left\lfloor \frac{n}{k}\right\rfloor} i = \frac{k}{2}\left\lfloor \frac{n}{k}\right\rfloor\left(\left\lfloor \frac{n}{k}\right\rfloor+1\right)\]

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);

« Back to problem overview