FireGarden FireGarden - 1 year ago 84
Python Question

Project Euler 23 - No matter what I do, my answer is far too big

Problem 23 asks for the sum of all numbers "not the sum of two abundant numers". We need only check numbers smaller than 28123. An integer n is abundant if its proper divisors sum to an integer greater than n - 12 is the first abundant number since 1+2+3+4+6 = 16 > 12. This makes 24 the smallest number which is a sum of 2 abundant numbers, so we want to exclude it from the sum.

Here's my python code, which I've tried many variations of, but using the same idea:

import math

def divisors_of(n):
for i in range(2,int(math.sqrt(n))+1):
if i**2 == n:
elif n%i == 0:
return divs

def is_abun(n):
return sum(divisors_of(n))>n

numbers=[i for i in range(1,28123)]

for i in numbers:
for j in range(1,i):
if is_abun(j) and is_abun(i-j):


The idea is simply that if j and i-j are abundant numbers, then of course j + (i-j) = i is a sum of abundant numbers, so I remove it from my list of numbers. Then I sum over all remaining numbers. I don't see how this could possibly fail. However, the result should be (gotten from another source) 4179871, while I always get something in the ballpark of 197711987, which is over 47 times too large.

I really cannot understand how this fails to generate the correct result. There must be some line which isn't doing what I think it is, but everything here is just too simple for me to be suspicious of them. I thought the most likely error would be in calculating the abundant numbers, but I am almost completely sure that part's correct (if I get the code as is to generate a list of abundant numbers less than 28123, I get a list of length 6965, which is how many abundant numbers less than 28123 WolframAlpha claims).

Answer Source

The problem is that you are modifying the list numbers while you are iterating over it. This results in you removing less numbers than what you expect.

You should iterate over a copy of it:

for i in list(numbers):
    for j in range(1,i):
        if is_abun(j) and is_abun(i-j):

To understand what's happening consider this:

>>> numbers = list(range(10))
>>> for i in numbers:
...     if i%2 == 0:
...         numbers.remove(i)
...     print(i)

As you can see the for loop only iterates over even numbers. That's because the for loop above is roughly equivalent to the following:

i = 0
while i < len(numbers):
    number = numbers[i]
    if number % 2 == 0:
    i += 1

So the first time you have i = 0 and thus number = 0, you remove the 0 from numbers so now you have numbers = [1,2,3,4,..., 9]. Note how the value 1 ended up in position 0, so the next iteration we have i = 1 and numbers[1] == [1,2,3,4,...,9][1] == 2 so we have skipped the number 1!

Everytime you remove a number the list is modified and if this modification leads to the items being shifted to the left you are effectively skipping them. That's why you want to iterate over a copy of the list: in this way the modifications to the original list do not affect the numbers "yielded" during iteration..

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download