Function to return the sum of multiples within a range

Question

Project Euler problem 1 says:

Find the sum of all the multiples of 3 or 5 below 1000.

I have written a program that will return the sum of the multiples of any list of positive integers. So for example if I wanted to know the sum of every integer that was a multiple of 3 and 5 that is less than 10 I would add 3,5,6, and 9 to get 23.

My function can do this for any number of positive integers, between any range that starts from 1.

# Function to return sum of multiples that are within a certain range
def MultiplesSum(multiple, end, start=1):
    mSum = 0
    naturals = range(start, end)
    offset = -start 
    if start == 0:
      raise ZeroDivisionError('Cannot start with the number 0')
    for num in multiple:
      for i in naturals:
        if i % num == 0 and naturals[i+offset] != 0:
          # print mSum,"+", i,"=",i+mSum
          mSum += i
          naturals[i+offset] = 0
        i += 1
    return mSum

problem1 = MultiplesSum([3,5,2], 16)
print problem1
# prints 88

Answer 1

Simpler implementation

You don't need naturals at all, and offset either. You could make the outer loop iterate over the range(start, end), and for each value check if it can be divided by any one of nums, and add to the sum.

msum = 0
for i in range(start, end):
    for num in nums:
        if i % num == 0:
            msum += i
            break
return msum

API

The interface of your function is not intuitive:

• The range start parameter goes after the range end parameter. That's not intuitive. Consider how Python's range works:

  • With one arg, the first arg is the end of the range
  • With two args, the first arg is the start, the second is the end of the range. It's natural that way

  I suggest to follow that example

• The first arg is called "multiple", singular. It's not a multiple. It's a collection of numbers. So nums would be a better name, and it would make it easier for readers to understand how to use this function

Input validation

In this part:

if start == 0:
  raise ZeroDivisionError('Cannot start with the number 0')

The zero division error is inappropriate. You did not divide by zero, and it won't make sense for callers to catch this exception and handle it. In other languages this should be an IllegalArgumentException, in Python ValueError would be more appropriate. The real problem is not division by zero, but inappropriate use of the function.

But then, why is start=0 inappropriate? I see nothing wrong with that. What would be wrong is having 0 in nums. That's what you should validate instead.

Coding style

The recommended practice is to use snake_case for function names, not CamelCase. See more coding style recommendations in PEP8.

Answer 2

If there are \$m\$ numbers in multiple and \$n\$ numbers in the range from start to end, then the function in the original post takes \$O(mn)\$. There's an alternative algorithm, using the inclusion–exclusion principle, that takes \$O(m2^m)\$, which is faster when \$2^m < n\$.

from fractions import gcd
from functools import reduce
from itertools import combinations

def lcm(seq):
    """Return the lowest common multiple of the numbers in the sequence."""
    return reduce(lambda a, b: a * b // gcd(a, b), seq)

def sum_multiples(numbers, start, stop):
    """Return the sum of all values between start (inclusive) and stop
    (exclusive) that are multiples of any values in the sequence numbers.

    """
    result, sign = 0, 1
    for i in range(1, len(numbers) + 1):
        for c in combinations(numbers, i):
            m = lcm(c)
            a = (start + m - 1) // m
            n = (stop + m - 1) // m - a
            result += sign * (a * n + (n - 1) * n // 2) * m
        sign = -sign
    return result

Answer 3

One big problem I see with your code is that you're using range to construct a data structure with the entire range of possible numbers in it. This could lead to huge memory requirements if start is far from end. A better choice would be to put the multiples you've already used into a dict (dictionary).

It's also suboptimal to check every single natural number between start and end for divisibility. for ... in ... is a useful tool, but it's not always applicable. This is one instance where using a counter would be preferable, since you could just add num to the counter each time and not have to check (you'd of course have to do the modulo once in order to get the right starting point).

Answer 4

I would suggest a simpler solution because Python is 'battery-included':

def multiple_sum(start, end, step):
    return sum(range(start + (start % step), end, step))

This makes use of (fast) built-ins and reads like pseudocode.