Project Euler #1 Sum of multiples of 3 and 5 python implementation 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?
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