Project Euler problem 1 in Python - Multiples of 3 and 5

Question

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)

Answer 1

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

Answer 2

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

valid = set([])

for i in range(3, end, 3):
  valid.add(i)

for i in range(5, end, 5):
  valid.add(i)

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

g.d.d.c's solution is slightly redundant in that it checks numbers that are multiples of 3 and 5 twice. I was wondering about optimizations to this, so this is slightly longer than a comment, but not really an answer in itself, as it totally relies on g.d.d.c's awesome answer as inspiration.

If you add multiples to the valid list for the multiple "3" and then do another pass over the whole list (1-1000) for the multiple "5" then you do experience some redundancy.

The order in which you add them:

 add 3-multiples first
 add 5 multiples second

will matter (albeit slightly) if you want to check if the number exists in the list or not.

That is, if your algorithm is something like

add 3-multiples to the list

add 5-multiples to the list if they don't collide

it will perform slightly worse than

add 5-multiples to the list

add 3-multiples to the list if they don't collide

namely, because there are more 3-multiples than 5-multiples, and so you are doing more "if they don't collide" checks.

So, here are some thoughts to keep in mind, in terms of optimization:

• It would be best if we could iterate through the list once
• It would be best if we didn't check numbers that weren't multiples of 3 nor 5.

One possible way is to notice the frequency of the multiples. That is, notice that the LCM (least-common multiple) of 3 and 5 is 15:

3   6  9   12  15  18  21  24   27  30
               ||                   ||
  5     10     15     20     25     30

Thus, you should want to, in the optimal case, want to use the frequency representation of multiples of 3 and 5 in the range (1,15) over and over until you reach 1000. (really 1005 which is divided by 15 evenly 67 times).

So, you want, for each iteration of this frequency representation:

the numbers at: 3 5 6 9 10 12 15

Your frequencies occur (I'm sorta making up the vocab for this, so please correct me if there are better math-y words) at starting indexes from 0k + 1 to 67k (1 to 1005) [technically 66k]

And you want the numbers at positions 3, 5, 6, 9, 10, 12, and 15 enumerating from the index.

Thus,

for (freq_index = 0; freq_index < 66; ++freq_index) {
    valid.add(15*freq_index + 3);
    valid.add(15*freq_index + 5);
    valid.add(15*freq_index + 6);
    valid.add(15*freq_index + 9);
    valid.add(15*freq_index + 10);
    valid.add(15*freq_index + 12);
    valid.add(15*freq_index + 15); //also the first term of the next indexed range
}

and we have eliminated redundancy

=)

---

Exercise for the astute / determined programmer:
Write a function that takes three integers as arguments, x y z and, without redundancy, finds all the multiples of x and of y in the range from 1 to z.
(basically a generalization of what I did above).

Answer 7

Using a generator is also possible :

print sum(n for n in range(1000) if n % 3 == 0 or n % 5 == 0)

Note that intent is not really clear here. For shared code, I would prefer something like

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

print euler001(1000)

Answer 8

The list comprehension one is an awesome solution, but making use of set is a lot faster:

from __future__ import print_function

def euler_001(limit):
    s1, s2 = set(range(0, limit, 3)), set(range(0, limit, 5))

    return sum(s1.union(s2))

print(euler_001(1000))

Answer 9

I used a slightly simpler method, but essentially did the same thing:

total = 0

for n in range(3,1000):
    if n % 3 == 0:
        total += n
    elif n % 5 == 0:
        total += n


print total

The elif makes sure that you only count any factor/divisor once.