According to Project Euler Problem #1If 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 233168The following is my code, which gives me the right answerimport timestart = (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() - startprint(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?
Project Euler problem #1 in Python 3
python;programming challenge;python 3.x
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 NumbersThe nth triangular number is a sum of integers from 1 to n. There are several proofs that show that these sums are equivalent to (n + 1) * n / 2, so no need to sum up all of the integers when all you need is a single multiply and divide.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. It's simply a sum of all multiples of three from 3 to n:3 + 6 + 9 + 12 + ... + nNote 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 integer)def sum_mul_less_than(m, n):    return (m * (n//m + 1) * (n//m)) // 2Now we can just add the multiples of three and five and be sure to 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 sConstant time is INCREDIBLY faster than linear time, \$O(n)\$. This solution can handle astronomically large inputs much larger than even 10**30.Edit: General caseAssuming the list of multiples could be 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.from itertools import combinationsfrom functools import reducedef geo(nums):    '''Multiply a list of numbers together'''    return reduce(lambda x, y: x*y, nums)def getmul(n, args):    n -= 1    s = 0    # remove the larger multiples from args 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