53
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Are you trying to optimize the algorithm or the code itself? \$\endgroup\$ – Joe Phillips Jan 19 '11 at 21:06
  • \$\begingroup\$ @JoePhillips: Why not both? ;) \$\endgroup\$ – Zolomon Jan 19 '11 at 21:07
  • \$\begingroup\$ @JoePhillips: the algorithm. it currently checks every single integer between 3 and 1000. \$\endgroup\$ – Robert S Ciaccio Jan 19 '11 at 21:08
  • \$\begingroup\$ @Zolomon: good point, either type of answer would be helpful. \$\endgroup\$ – Robert S Ciaccio Jan 19 '11 at 21:09
  • \$\begingroup\$ Just a note. The detailed explanation for Richard's Answer on Wikipedia may be helpful if you didn't already understand the Math. See here. \$\endgroup\$ – user853 Jan 27 '11 at 18:12
42
\$\begingroup\$

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))
\$\endgroup\$
  • 9
    \$\begingroup\$ this is obviously most efficient. i was about to post this as a one liner but i prefer the way you factored it. still, would sum_multiples_of_n_below_k be the appropriate name? they are not n's factors, they are its multiples \$\endgroup\$ – jon_darkstar May 4 '11 at 15:19
27
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @gddc: nice, I didn't even know you could specify an increment in a range like that. \$\endgroup\$ – Robert S Ciaccio Jan 19 '11 at 21:25
  • \$\begingroup\$ That's also what I would do now. \$\endgroup\$ – Basil Jan 19 '11 at 21:26
  • \$\begingroup\$ @calavera - range() is a great function ... the optional step as a 3rd parameter can save tons of iterations. \$\endgroup\$ – g.d.d.c Jan 19 '11 at 21:26
  • \$\begingroup\$ docs.python.org/library/functions.html#range just for good measure \$\endgroup\$ – sova Jan 19 '11 at 22:03
  • 2
    \$\begingroup\$ Also by using the set.update method you could shed the loop and write someting like: valid.update(xrange(3, end, 3)) \$\endgroup\$ – Mr Shark Jan 27 '11 at 19:38
17
\$\begingroup\$

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.

\$\endgroup\$
15
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ do you think it would be faster or slow to allow the repetitive 5's to be added and then substract the 15's? we would lose end/5 divisibility checks and it costs only add/15 subtractions \$\endgroup\$ – jon_darkstar May 4 '11 at 15:24
8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I'll have to check the documentation to be sure, but I believe the set.add() method uses a binary lookup to determine whether or not the new element exists already. If that's correct then the order you check the multiples of 3's or 5's won't matter - you have an identical number of binary lookups. If you can implement a solution that rules out double-checks for multiples of both you may net an improvement. \$\endgroup\$ – g.d.d.c Jan 19 '11 at 22:44
  • 1
    \$\begingroup\$ @g.d.d.c: Ah, good point. I was thinking more language-agnostically, since the most primitive implementation wouldn't do it efficiently. An interesting aside about the python <code>.add()</code> function from a google: indefinitestudies.org/2009/03/11/dont-use-setadd-in-python \$\endgroup\$ – sova Jan 20 '11 at 1:14
  • \$\begingroup\$ @sova - Thanks for the link on the union operator. I hadn't ever encountered that and usually my sets are small enough they wouldn't suffer from the performance penalty, but knowing alternatives is always great. \$\endgroup\$ – g.d.d.c Jan 20 '11 at 16:46
  • \$\begingroup\$ @g.d.d.c also, the solution above does indeed rule out double-checks for multiples of both, it figures out the minimal frequency at which you can repeat the pattern for digits (up to the LCM of the two digits). Each valid multiple of 3, 5, or both, is "checked" (actually, not really checked, just added) only once. \$\endgroup\$ – sova Jan 20 '11 at 22:45
  • \$\begingroup\$ @g.d.d.c python's set is based on a hash table. It is not going to use a binary lookup. Instead it will do a hash table lookup. \$\endgroup\$ – Winston Ewert Feb 24 '11 at 17:57
8
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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))
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ (did the same thing: The order in which answers are shown is bound to change, and you might be referring to the question: please disambiguate with a quote or a hyperlink (e.g., from the share-link at the end of each post).) \$\endgroup\$ – greybeard Sep 4 '16 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.