Project Euler problem #1 in Python 3

Question

According to Project Euler Problem #1

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. The answer being 233168

The following is my code, which gives me the right answer

import time
start = (time.time())

def getmul(x, *args):
    s=0
    for i in range(1,x):
        for arg in args:
            if (i%arg==0):
                s+=i
                break
    return(s)


res = getmul(1000,3,5)
end = time.time() - start
print(res, end)

I built the function in such a way that arbitrary arguments can be inputted and the result obtained. Are there more efficient ways of solving this problem?

Answer 1

Yes there is a faster way! Your solution is \$O(n)\$, but a \$O(1)\$ (constant time) solution exists.

This is one of my favorite problems since you don't need a computer to solve it.

---

Triangular Numbers

The nth triangular number is a sum of integers from 1 to n. There are several proofs that show this sum is equivalent to (n + 1) * n / 2.

To get down to constant time, one needs to note that the sum of all multiples of 3 less than n is very similar to a triangular number. Here's a sum denoting what we want:

3 + 6 + 9 + 12 + ... + 3*(n // 3)

Note the integer division //

If we factor a 3 out of this sum:

3(1) + 3(2) + 3(3) + 3(4) + ... + 3(n//3)

We get three times a triangular number!

3(1 + 2 + 3 + 4 + ... + n//3)

Which can be simplified down to:

3 * ((n//3 + 1) * n//3 // 2)

The same can be done for 5 (or any natural number)

def sum_mul_less_than(m, n):
    return (m * (n//m + 1) * (n//m)) // 2

Now we add the multiples of three and five and subtract the extra set of multiples of 15 (I like how clever the break was in your code for this).

def getmul_3_5(n): # this solution is harder to generalize for any multiple
    n -= 1 # we don't want to include n
    s = 0
    s += sum_mul_less_than(3, n)
    s += sum_mul_less_than(5, n)
    s -= sum_mul_less_than(15, n)
    return s

Constant time is INCREDIBLY faster than linear time, \$O(n)\$. This solution can handle astronomically large inputs bigger than 10**30 even.

---

Edit: General case

Assuming the list of multiples could be of any size, you should get rid of the unpacking argument list operator since it's less convenient to users. I came up with a solution that is \$O(2^m)\$ where m is the number of multiples. Your solution is \$O(nm)\$ which would be asymptotically faster around \$n < 2^{m-1}\$, so you could fine tune this line and use the strategy pattern to pick the faster algorithm on a case by case basis.

First I removed all of the redundant multiples, (e.g. 4 if 2 is in m since any number divisible by 4 is already counted by 2). Then I found every possible multiple combination of the numbers in m.

Combinations with odd lengths are added; combinations with even lengths are subtracted (the inclusion exclusion principle as noted by user Gareth Rees).

from itertools import combinations
from functools import reduce

def geo(nums):
    '''Multiply a list of numbers together'''
    return reduce(lambda x, y: x*y, nums)

def getmul(n, args):
    n -= 1
    s = 0

    # removing the redundant multiples from args is left as an excercise
    # O(m^2)

    # there are 2^len(args) combinations of args
    for i in range(1, len(args) + 1):
        for c in combinations(args, i):
            if i % 2 == 1:
                s += sum_mul_less_than(geo(c), n)
            else:
                s -= sum_mul_less_than(geo(c), n)
    return s

Answer 2

More pythonic code

Even when not going down the constant time route, this code can be significantly shortened by using Python's generator expressions:

def getmul(x, *args):
    return sum(i for i in range(1, x) if any(i % arg == 0 for arg in args))

However, while this is way easier to read, in my opinion, this is about three times slower than your code (which quite surprised me). The reason is the continuous creation and destruction of frames for the any scope, as explained in the answer to this question about exactly this code.

Style

Note that you don't need to surround the argument to return in parenthesis, return x is just fine. The same is true for the if statement.

Here is your code getting rid of unneeded parenthesis and some added whitespace as recommended by Python's official style-guide, PEP8:

import time


def getmul(x, *args):
    s = 0
    for i in range(1, x):
        for arg in args:
            if i % arg == 0:
                s += i
                break
    return s


if __name__ == "__main__":
    start = time.time()    
    res = getmul(1000, 3, 5)
    end = time.time() - start
    print(res, end)

I also added a if __name__ == "__main__": guard to allow importing this function from another script without executing the test. The timing is now also only around the actual function call.