Project Euler 1 Solution: 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.
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);