Problem 1 Project Euler, which asks you to find the sum of all multiples of 3 or 5 below 1000, so 3 + 5 + 6 + 9, etc.
The correct answer is 233168 but my code is returning 266333.
I’m not looking to use a different method, I’m wondering why this code isn’t working as is, from the debugging that I did it looks as everything that I am expecting to see is there.
numArray = [] a = 0 b = 0 total = 0 totala = 0 totalb = 0 #numArray a and b were for testing purposes to make sure array was correct length numArraya = [] numArrayb = [] while a < 1000: numArray.append(a) numArraya.append(a) a += 3 #expecting to get 334, returns 334 #print (len(numArraya)) while b < 1000: numArray.append(b) numArrayb.append(b) b += 5 #expecting 200, returns 200 #print (len(numArrayb)) #for numa in numArraya: # totala += numa #print (totala) #for numb in numArrayb: # totalb += numb #print (totalb) for num in numArray: total += num print (total)
Advertisement
Answer
Your solution includes numbers that are multiples of both 3 and 5, twice. You are adding 15, 30, 45, etc. twice to the final sum:
>>> 266333 - 233168 # the difference between the correct answer and yours 33165 >>> sum(range(0, 1000, 15)) # is the same as the sum of all multiples of 15 < 1000 33165
Your solution can be fixed by testing if b
is already present in numArray
:
while b < 1000: if b not in numArray: numArray.append(b) numArrayb.append(b) b += 5
The simpler solution is to just loop from 0 to 999 and test each number with the %
modulus operator; if the outcome is 0, the left-hand side number is divisible by the right-hand side argument. Together with the sum()
built-in function and a generator expression, that becomes:
sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0)
Your approach, if cast as a set problem, is fine too:
sum(set(range(0, 1000, 3)).union(range(0, 1000, 5)))
Both approaches still loop and thus will take more time as the numbers grow. There is however a mathematical solution that takes constant time.
Note that your ‘bug’ hints at a possible path; if the sum of all multiples of 3 and multiples of 5 below 1000 was off by the sum of all multiples of (3 times 5 == 15) below 1000, then if you have a simple formula to calculate the sum of any multiple of x below n then you can calculate the solution to this problem by adding the sums for 3 and 5 and subtracting the sum for 15.
In other words, if f(x, n)
calculates the total sum of all multiples of x
below n
, then the solution to Euler #1 is equal to f(3, 1000) + f(5, 1000) - f(3 * 5, 1000)
.
In this case, f
is the triangular number of the divisor of n over x, and x:
def f(x, n): """sum of all multiples of x below n""" divisor = (n - 1) // x return (divisor * x * (divisor + 1)) // 2
giving you a straight, linear time outcome:
>>> def f(x, n): ... """sum of all multiples of x below n""" ... divisor = (n - 1) // x ... return (divisor * x * (divisor + 1)) // 2 ... >>> f(3, 1000) + f(5, 1000) - f(3 * 5, 1000) 233168