current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 9 down vote favorite

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?

share|improve this question

2 Answers 2

up vote 9 down vote accepted

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
share|improve this answer
    
I would still prefer some better name than sum35 :) –  CodeYogi 12 hours ago
    
Agreed, but naming things is hard. :D I'd probably call it euler_1 or something, tbh. –  tzaman 12 hours ago
    
Very true! Naming and caching are two most difficult problems in CS. –  CodeYogi 12 hours ago
up vote 6 down vote

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.

share|improve this answer
    
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 yesterday
    
Try more examples on paper till you understand the idea better. ;) –  Alex Palcuie yesterday
    
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 yesterday
    
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 yesterday
1  
I fear it should be no_of_multiples = limit - 1 // num see @tzaman's solution. –  CodeYogi yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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