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.



In [1]:

    
from __future__ import print_function



In [2]:

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



In [3]:

    
n=10
foo(n)









    Out[3]:





23



In [4]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 358 µs per loop






    Out[4]:





233168



In [5]:

    
def foo(n):
    total = 0
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total



In [6]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 251 µs per loop






    Out[6]:





233168

It is surprising that the naive code immediately above is faster than the functional programming version.



In [7]:

    
def foo(n):
    a = []
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            a.append(i)
    return sum(a)



In [8]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 304 µs per loop






    Out[8]:





233168



In [9]:

    
def foo(n):
    return sum([i for i in range(n) if i % 3 == 0 or i % 5 == 0])



In [10]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 257 µs per loop






    Out[10]:





233168



In [11]:

    
def foo(n):
    return sum((i for i in range(n) if i % 3 == 0 or i % 5 == 0))



In [12]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 261 µs per loop






    Out[12]:





233168



In [13]:

    
def foo(n):
    return sum((j for j in (i for i in range(n) if i % 3 == 0) if j % 5 == 0))



In [14]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 221 µs per loop






    Out[14]:





33165

Wow, the nested generator expressions above were the fastest yet, also ugliest, and irredeemably wrong. The flaw is that only numbers that are multiples of both 3 and 5 are summed. I.e., the bug was 'and' instead of 'or'.

Thanks to Eric for catching that cells 13 through 16 are broken. It is easy to fast when one is wrong. So nevermind cells 13 through 16.

The unnested list comprehension was faster than the unnested generator expression, so let's try nested list comprehensions.



In [15]:

    
def foo(n):
    return sum([j for j in [i for i in range(n) if i % 3 == 0] if j % 5 == 0])



In [16]:

    
n=1000
%timeit foo(n)
foo(n)









    



10000 loops, best of 3: 195 µs per loop






    Out[16]:





33165

I expected the nested list comprehensions to be a little bit faster than the nested generator expressions, so I was surprised by the big speed increase.

Let's play with generators more.



In [17]:

    
def threes_or_fives(gen):
    for i in gen:
        if i % 3 == 0:
            yield i
        elif i % 5 == 0:
            yield i

def foo(n):
    return sum(threes_or_fives(range(n)))



In [18]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 254 µs per loop






    Out[18]:





233168



In [19]:

    
def threes_or_fives(gen):
    for i in gen:
        if i % 3 == 0 or i % 5 == 0:
            yield i

def foo(n):
    return sum(threes_or_fives(range(n)))



In [20]:

    
n=1000
%timeit foo(n)
foo(n)









    



1000 loops, best of 3: 262 µs per loop






    Out[20]:





233168

It is surprising that the naive verbose generator function with two if statements is faster than the generator function with the combined if statement.

I thought of one more way later, using sets, that should be much more elegant.



In [21]:

    
def foo(n):
    return sum(set(range(0, n, 3)) | set(range(0, n, 5)))



In [22]:

    
n=1000
%timeit foo(n)
foo(n)









    



10000 loops, best of 3: 62.6 µs per loop






    Out[22]:





233168

Holy smokes! It is easier to read, but I did not expect it to be so fast.

I can not resist the temptation to generalize.



In [23]:

    
def foo(n, divisors):
    all_multiples = set([])
    for multiples in (set(range(0, n, divisor)) for divisor in divisors):
        all_multiples |= multiples
    return sum(multiples)



In [24]:

    
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)









    



10000 loops, best of 3: 58.8 µs per loop






    Out[24]:





99500

Thanks to Eric for catching that cells 23 and 24 are broken. I summed the wrong thing. This is fixed below.



In [25]:

    
def foo(n, divisors):
    all_multiples = set([])
    for multiples in (set(range(0, n, divisor)) for divisor in divisors):
        all_multiples |= multiples
    return sum(all_multiples)



In [26]:

    
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)









    



10000 loops, best of 3: 65.6 µs per loop






    Out[26]:





233168

That is terribly ugly. I was trying to do some kind of union of a set comprehension, but that is just not available as far as I know.

When I give up on that, it becomes simple below.



In [27]:

    
def foo(n, divisors):
    multiples = set([])
    for divisor in divisors:
        multiples |= set(range(0, n, divisor))
    return sum(multiples)



In [28]:

    
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)









    



10000 loops, best of 3: 64 µs per loop






    Out[28]:





233168

I will have another go at the union thing, this time as a function.



In [29]:

    
def union(sets):
    u = set([])
    for s in sets:
        u |= s
    return u



In [30]:

    
def foo(n, divisors):
    return sum(union(set(range(0, n, d)) for d in divisors))



In [31]:

    
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)









    



10000 loops, best of 3: 70.6 µs per loop






    Out[31]:





233168

It works, but is not as readable, so forget it.

Of course, none of this compares to what I did last year.