# 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

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

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.

• 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. – CodeYogi Sep 15 '15 at 15:25
• Try more examples on paper till you understand the idea better. ;) – Alex Palcuie Sep 15 '15 at 15:27
• 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. – CodeYogi Sep 15 '15 at 15:27
• 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. – Alex Palcuie Sep 15 '15 at 15:33