Project Euler problem #1 in Python 3 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?
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 &lt; 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