Question
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
Multiples of \(3\) are \(3,6,9,\dots,3i\) such that \(3i \leq N\) or \(i \leq N/3\). Thus we can write the sum of the multiples of \(3\) as \(S_{3} = 3\times (1+2+\dots +N/3)\) or \(S_{3} = 3 \times (N/3)*(N/3+1)/2\). Similarly we can write the sum of the multiples of \(5\) as \(S_{5} = 5 \times (N/5)*(N/5+1)/2\).
\(S_3\) and \(S_5\) will give us the sum of the multiples of \(3\) and \(5\), but there will be common multiples for \(3\) and \(5\) which will be added twice in the sum. We need to subtract those common multiples from the sum to get the correct answer. To do this we find the [Least Common Multiple] of the two numbers which is \(15\). Then the sum of the common multiples of \(3\) and \(5\) will be \(S_{15} = 15 \times (N/15)*(N/15+1)/2\).
We can now get the final sum as \(S = S_3 + S_5 - S_{15}\).
Find the code [here] .