Skip to content
Advertisement

Why is my Project Euler problem #1 code returning the wrong result?

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
Advertisement