project euler1

Multiples of 33 or 55

If we list all the natural numbers below 1010 that are multiples of 33 or 55, we get 3,5,63, 5, 6 and 99. The sum of these multiples is 2323.

Find the sum of all the multiples of 33 or 55 below 10001000.

Solution

We can use the fact that the sum of the first nn natural numbers is n(n+1)2\frac{n(n+1)}{2} to solve this problem.

The sum of all the multiples of 33 below 10001000 is

3+6+9+⋯+999=3(1+2+3+⋯+333)=3⋅333⋅3342.3 + 6 + 9 + \cdots + 999 = 3(1 + 2 + 3 + \cdots + 333) = 3 \cdot \frac{333 \cdot 334}{2}.

Similarly, the sum of all the multiples of 55 below 10001000 is 5⋅199⋅20025 \cdot \frac{199 \cdot 200}{2}.

However, we have counted the multiples of 1515 twice, so we must subtract them once. The sum of all the multiples of 1515 below 10001000 is 15⋅66⋅67215 \cdot \frac{66 \cdot 67}{2}. Thus, the answer is

3⋅333⋅3342+5⋅199⋅2002−15⋅66⋅672=233168.3 \cdot \frac{333 \cdot 334}{2} + 5 \cdot \frac{199 \cdot 200}{2} - 15 \cdot \frac{66 \cdot 67}{2} = 233168.