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

• CodeYogi: I would still prefer some better name than sum35 :)
• tzaman: Agreed, but naming things is hard. :D I'd probably call it euler_1 or something, tbh.
• CodeYogi: Very true! Naming and caching are two most difficult problems in CS.

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.

• CodeYogi: For example I have 15 then multiples of 3=3, 6, 9, 12, 15, multiples of 5=5, 10, 15 and multiples of 15=15. Hmm, it seems to work.
• Alex Palcuie: Try more examples on paper till you understand the idea better. ;)
• CodeYogi: Also, can you please help me to find the running time of my solution. Because in general the running time is wrt to input size but in my case I have just constant numbers.
• Alex Palcuie: First, running time is different from algorithm complexity. Read more here. If you want to learn more about complexities just search on the internet and read a book.