FireGarden - 1 month ago 5x

Python Question

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):

divs=[1]

for i in range(2,int(math.sqrt(n))+1):

if i**2 == n:

divs.append(i)

elif n%i == 0:

divs.append(i)

divs.append(n//i)

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):

numbers.remove(i)

break

print(sum(numbers))

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

Answer

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):
numbers.remove(i)
break
```

To understand what's happening consider this:

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

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:
numbers.remove(number)
print(number)
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..

Source (Stackoverflow)

Comments