Project Euler #1 Sum of multiples of 3 and 5 python implementation

Question

Given:

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.

My Solution:

def sum_multiples(num, limit):
    """ Calculates the sum of multiples of a given number.
    Args:
        num: The multiple.
        limit: The upper limit.
    Returns:
        The sum of the terms of a given multiple.
    """
    sum = 0
    for i in xrange(num, limit, num):
        sum += i
    return sum

def sum(limit):
    return (sum_multiples(3, limit) +
            sum_multiples(5, limit) -
            sum_multiples(15, limit))

print sum(1000)

Is there any better or more pythonic way? I have used generators for a very large calculation. Also, how can I get the running time for a given N?

Answer 1

It'd be more pythonic to use the built-in sum function instead of writing one yourself:

sum(xrange(num, limit, num))

However, this is still doing way too much work -- you don't need to do a for-loop for a series sum, there's a closed-form solution:

def sum_multiples(n, lim):
    last = (lim - 1) // n
    return n * (last) * (last+1) // 2

EDIT: Also, don't call your own function sum, since you hide the built-in one that way.

def sum35(limit):
    return (sum_multiples(3, limit) +
            sum_multiples(5, limit) -
            sum_multiples(15, limit))

print sum35(10)   # 23
print sum35(1000) # 233168

Answer 2

Your Python code looks good, but your solution can be slow for large values. You can compute the sum of multiples in O(1). We can first observe there are floor(limit / num) terms that are divisible by num and smaller then limit. Finally we can calculate the result using the Gauss sum formula.

def sum_multiples(num, limit):
  no_of_multiples = (limit - 1) // num
  return no_of_multiples * (no_of_multiples + 1) / 2 * num

For your example sum_multiples(3, 10), the no_of_multiples will be 3 (those are 3, 6, 9) and we can express their sum as:

3 + 6 + 9 = 3 * (1 + 2 + 3) = 3 * ((3 * 4) / 2) 

You can get the running time under Linux by using the time utility, writing in your terminal time python3 script.py for example.