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