# Project Euler problem 1 in Python – Multiples of 3 and 5

Posted on

Problem

I’d like suggestions for optimizing this brute force solution to problem 1. The algorithm currently checks every integer between 3 and 1000. I’d like to cut as many unnecessary calls to `isMultiple` as possible:

``````'''
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 = 1000

def Solution01():
'''
Solved by brute force
#OPTIMIZE
'''
sum = 0
for i in range(3, end):
if isMultiple(i):
sum += i
print(sum)

def isMultiple(i):
return (i % 3 == 0) or (i % 5 == 0)
``````

Solution

The sum 3+6+9+12+…+999 = 3(1+2+3+…+333) = 3 (n(n+1))/2 for n = 333. And 333 = 1000/3, where “/” is integral arithmetic.

Also, note that multiples of 15 are counted twice.

So

``````def sum_factors_of_n_below_k(k, n):
m = (k-1) // n
return n * m * (m+1) // 2

def solution_01():
return (sum_factors_of_n_below_k(1000, 3) +
sum_factors_of_n_below_k(1000, 5) -
sum_factors_of_n_below_k(1000, 15))
``````

I think the best way to cut out possible checks is something like this:

``````valid = set([])

for i in range(3, end, 3):

for i in range(5, end, 5):

total = sum(valid)
``````

There’s still a bit of redundancy (numbers which are multiples of both 3 and 5 are checked twice) but it’s minimal.

I would get rid of the `for` loops and use `sum` on generator expressions.

``````def solution_01(n):
partialsum = sum(xrange(3, n, 3))
return partialsum + sum(x for x in xrange(5, n, 5) if x % 3)
``````

Note that we’re using `xrange` instead of `range` for python 2. I have never seen a case where this isn’t faster for a `for` loop or generator expression. Also consuming a generator expression with `sum` should be faster than adding them up manually in a `for` loop.

If you wanted to do it with sets, then there’s still no need for `for` loops

``````def solution_01(n):
values = set(range(3, n, 3)) | set(range(5, n, 5))
return sum(values)
``````

Here, we’re just passing the multiples to the set constructor, taking the union of the two sets and returning their sum. Here, I’m using `range` instead of `xrange`. For some reason, I’ve seen that it’s faster when passing to `list`. I guess it would be faster for `set` as well. You would probably want to benchmark though.

Well, this is an answer to a Project Euler question after all, so perhaps the best solution is basically a pencil-paper one.

``````sum(i for i in range(n + 1)) # sums all numbers from zero to n
``````

is a triangular number, the same as

``````n * (n + 1) / 2
``````

This is the triangular function we all know and love. Rather, more formally,

``````triangle(n) = n * (n + 1) / 2
``````

With that in mind, we next note that the sum of the series

``````3, 6, 9, 12, 15, 18, 21, 24, ...
``````

is 3 * the above triangle function. And the sums of

``````5, 10, 15, 20, 25, 30, 35, ...
``````

are 5 * the triangle function. We however have one problem with these current sums, since a number like 15 or 30 would be counted in each triangle number. Not to worry, the inclusion-exclusion principle comes to the rescue! The sum of

``````15, 30, 45 ,60, 75, 90, 105, ...
``````

is 15 * the triangle function. Well, if this so far makes little sense don’t worry. Finding the sum of the series from 1 up to n, incrementing by k, is but

``````triangle_with_increments(n, k = 1) = k * (n/k) * (n/k + 1) / 2
``````

with this, and the inclusion-exclusion principle, the final answer is but

``````triangle_with_increments(100, 5) + triangle_with_increments(100, 3) - triangle_with_increments(100, 15)
``````

Wow. Who’da thunk? an n complexity problem suddenly became a constant time one. That’s what I call optimization IMHO :P. But in all seriousness, Project Euler asks you to answer problems in really the lowest computational complexity possible.

I would do it like this:

``````total = 0

for i in range(3, end, 3):
total += i

for i in range(5, end, 5):
if i % 3 != 0: # Only add the number if it hasn't already
total += i   # been added as a multiple of 3
``````

The basic approach is the same as g.d.d.c’s: iterate all the multiples of 3, then 5. However instead of using a set to remove duplicates, we simply check that the multiples of 5 aren’t also multiples of 3. This has the following upsides:

1. Checking divisibility is less expensive than adding to a set.
2. We build the total up incrementally, so we don’t need a separate call to sum at the end.
3. We got rid of the set, so we only need constant space again.