Problem 1 | Jack Moody

Problem 1 - 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 999.

The Idea

Note that 3 divides 3, 6, 9, 12, ... and 5 divides 5, 10, ... while both numbers divide certain numbers (15, 30, 45, ...). Since 3 and 5 are both prime numbers, they only "collide" every 15, so we can find the sum of the numbers which are divisible by either 3 or 5 by summing the numbers divisible by either and then subtracting the instances where we double count (every 15). Because we are only concerned with numbers below 999, we will count to 999.

\sum_{i=1}^{\lfloor\frac{999}{3}\rfloor} 3i + \sum_{i=1}^{\lfloor\frac{999}{5}\rfloor} 5i - \sum_{i=1}^{\lfloor\frac{999}{15}\rfloor} 15i

Noting that this is simply an arithmetic sum, and the formula for an arithmetic sum of the form

\sum_{i=1}^{n} a_{n} = n\left(\frac{a_{1} + a_{n}}{2} \right)

we can calculate the formula above.

\text{Answer} = 333 \left(\frac{3 + 999}{2}\right) + 199 \left(\frac{5 + 995}{2}\right) - 66 \left(\frac{15 + 990}{2}\right)

Indirect Solution

One other possibility is to simply add all numbers that are divisible from 1 to 999 if they are divisible by 3 or 5. This is what is done in the code below.

The Code

Notes

The full utils module can be found on GitHub here