# Multiples of 3 and 5

This is the first post of a series entitled Project Euler In Under 0.1ms

### Project Euler #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.

### Common (and slow) solution

The most common, naive solution involves a simple loop from 0 to x, checking whether n is multiple of 3 or 5 and then adding n to the sum. Pretty straightforward:

def multiples_three_five(x):
s = 0
for n in range(x):
if n % 3 == 0 or n % 5 == 0:
s += n
return s

# Time spent: 497.477ms

### Stay put as a Pythonista

Things get worse if we’re not true Pythonistas and dare to use filter. It takes almost twice the time to complete compared to the previous one:

def multiples_three_five(x):
return sum(filter(lambda n: n % 3 == 0 or n % 5 == 0, range(x)))

# Time spent: 792.545ms

### A slightly better approach

Instead of looping up to x, we could loop until the maximum multiple of 3 or 5 that is less than x. As we want the maximum one, it should be multiple of 3, since 3 < 5. Just remember not to re-add “duplicate numbers”, those that are multiples of both 3 and 5:

def multiples_three_five(x):
s = 0
for n in range(1, int(x/3) + 1):
p = n * 3
if p < x:
s += p
p = n * 5
if p % 3 and p < x:
s += p
return s

# Time spent: 289.934ms

### A better approach

But, wait! We could just loop from 0 to x, 3 by 3, summing all values, then do the same 5 by 5 – but not re-adding dupes:

def multiples_three_five(x):
s = 0
for n in range(3, x, 3):
s += n
for n in range(5, x, 5):
if n % 3:
s += n
return s

# Time spent: 152.503ms

### Same approach improved a bit

We’re good re-adding duplicate numbers as long as we subtract them later:

def multiples_of_three_and_five(x):
s = 0
for n in range(3, x, 3):
s += n
for n in range(5, x, 5):
s += n
for n in range(15, x, 15):
s -= n
return s

# Time spent: 129.046ms

### Same approach improved some more

We can gain some precious milliseconds benefitting from Python’s fast addition. The following is around three times faster than the previous one:

def multiples_of_three_and_five(x):
return sum(range(3, x, 3)) + sum(range(5, x, 5)) - sum(range(15, x, 15))

# Time spent: 38.212ms

WOW! From 497.477ms down to 38.212ms! But even so, this is far from being fast. We’ve just saved hundreds of milliseconds. We need a completely different approach.

### Going under 0.1ms

Look at what we’ve got so far. Each of those sums is the sum of a series! And, as young Gauss brilliantly found out, we can write them as mathematical equations. Kudos, Johann Carl Friedrich Gauss.

Take S, for instance, the sum of all natural numbers from 1 to n. We can define it as:

$$^{(eq.\ 1)}\ \ \ S=\sum_{n=1}^{x}{n}=1+2+3+4+…+x = {x(x+1)\over2}$$

Analogously, we can state the following:

$$^{(eq.\ 2)}\ \ \ 5S=5\sum_{n=1}^{x}{n}=5+10+15+20+…+5x = 5{x(x+1)\over2}$$

Considering the above, to sum all natural numbers below 25 that are multiples of 5, we could just sum all of them up to 20, the 4th element (i.e. floor((25 - 1) / 5) = 4). Thus, defining x' = x - 1, we can use the following to obtain the sum of all multiples of 5 below x:

$$^{(eq.\ 3)}\ \ \ 5S'=5\sum_{n=1}^{\left\lfloor\frac{x'}{5}\right\rfloor}n=5\ \frac{{\left\lfloor\frac{x'}{5}\right\rfloor}({\left\lfloor\ \frac{x'}{5}\right\rfloor}+1)}{2}$$

Then we can take:

$$^{(eq.\ 4)}\ \ \left\lfloor\frac{x'}{5}\right\rfloor=\frac{x'-(x'\mod\ 5)}{5}$$

Replace it into equation 3 to end up with:

$$^{(eq.\ 5)}\ \ \ 5S'=\frac{\{x'-[(x')\mod\ 5]\}\{x'-[(x')\mod\ 5]+5\}}{10}$$

And solve the problem really fast:

def multiples_of_three_and_five(x):
x -= 1
s = ((x - x % 3) * (x - x % 3 + 3)) // 6
s += ((x - x % 5) * (x - x % 5 + 5)) // 10
s -= ((x - x % 15) * (x - x % 15 + 15)) // 30
return s

# Time spent: 0.019ms