# 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:

Analogously, we can state the following:

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`

:

Then we can take:

Replace it into equation 3 to end up with:

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
```

##### About the author

Pablo Aguiar is a software engineer and coffee geek from Brazil. He's curious about computers, maths and science. He enjoys a good coffee and loves literature. Read more...