<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 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.
Step1:  It is surprising that the naive code immediately above is faster than the functional programming version.
Step2:  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.
Step3:  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.
Step4:  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.
Step5:  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.
Step6:  Thanks to Eric for catching that cells 23 and 24 are broken. I summed the wrong thing. This is fixed below.
Step7:  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.
Step8:  I will have another go at the union thing, this time as a function.
<ASSISTANT_TASK:>
Python Code:
from __future__ import print_function
def foo(n):
    return sum(filter(lambda x: x % 3 == 0 or x % 5 == 0, range(n)))
n=10
foo(n)
n=1000
%timeit foo(n)
foo(n)
def foo(n):
    total = 0
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total
n=1000
%timeit foo(n)
foo(n)
Explanation: 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.
End of explanation
def foo(n):
    a = []
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            a.append(i)
    return sum(a)
n=1000
%timeit foo(n)
foo(n)
def foo(n):
    return sum([i for i in range(n) if i % 3 == 0 or i % 5 == 0])
n=1000
%timeit foo(n)
foo(n)
def foo(n):
    return sum((i for i in range(n) if i % 3 == 0 or i % 5 == 0))
n=1000
%timeit foo(n)
foo(n)
def foo(n):
    return sum((j for j in (i for i in range(n) if i % 3 == 0) if j % 5 == 0))
n=1000
%timeit foo(n)
foo(n)
Explanation: It is surprising that the naive code immediately above is faster than the functional programming version.
End of explanation
def foo(n):
    return sum([j for j in [i for i in range(n) if i % 3 == 0] if j % 5 == 0])
n=1000
%timeit foo(n)
foo(n)
Explanation: 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.
End of explanation
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)))
n=1000
%timeit foo(n)
foo(n)
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)))
n=1000
%timeit foo(n)
foo(n)
Explanation: 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.
End of explanation
def foo(n):
    return sum(set(range(0, n, 3)) | set(range(0, n, 5)))
n=1000
%timeit foo(n)
foo(n)
Explanation: 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.
End of explanation
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)
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)
Explanation: 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.
End of explanation
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)
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)
Explanation: Thanks to Eric for catching that cells 23 and 24 are broken. I summed the wrong thing. This is fixed below.
End of explanation
def foo(n, divisors):
    multiples = set([])
    for divisor in divisors:
        multiples |= set(range(0, n, divisor))
    return sum(multiples)
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)
Explanation: 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.
End of explanation
def union(sets):
    u = set([])
    for s in sets:
        u |= s
    return u
def foo(n, divisors):
    return sum(union(set(range(0, n, d)) for d in divisors))
n=1000
divisors = (3, 5)
%timeit foo(n, divisors)
foo(n, divisors)
Explanation: I will have another go at the union thing, this time as a function.
End of explanation
<END_TASK>