11
\$\begingroup\$

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?

\$\endgroup\$
11
\$\begingroup\$

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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