I apologise for the all too common Project Euler question, but I am genuinely stumped as to how the value that I'm getting even comes to be. I have since found an implementation that works, so I'm not looking for a fix but rather an explanation as to why I get that number at the end. The problem I'm referring to is this. It asks to find the sum of all positive integers that cannot be written as a sum of two abundant numbers. Below is my code:

from math import sqrt
import itertools

def primeFactors(n):
    # Returns dictionary with number of each prime divisor
    primes = {}
    count = 0
    while n % 2 == 0:
        count  = 1
        n = n / 2

    if count > 0:
        primes[2] = count

    for i in range(3, int(sqrt(n))   1, 2):
        while n % i == 0:
            if i not in primes:
                primes[i] = 1
            else: primes[i]  = 1
            n = n / i

    if n > 2:
        if n not in primes:
            primes[n] = 1
        else: primes[n]  = 1

    return primes

def SumProper(n):
    # Outputs sum of proper factors of n
    x = 1
    for key,value in primeFactors(n).items():
        x *= (key**(value   1) - 1) / (key - 1)
    y = x - n
    return int(y)

x = set(range(1,28124))

abundant = {i for i in range(1,14062) if SumProper(i)>i}
AbSums = {i j for i, j in itertools.product(abundant, repeat=2)}

y = x.difference(AbSums)
print(sum(y))

The answer that I keep getting is 31531501, whereas the correct solution is 4179871. All of my functions seem to work properly when tested, but after a bit of experimentation I've discovered that I seem to start undercounting the abundant numbers after the 14,000 mark. I have no idea why. If somebody could explain where the error is and how the 31531501 number comes about, I'd be extremely grateful. Thanks!

P.S. I understand the code may not be optimal at this stage, but my current goal is to understand the origin of the error, and I can work on optimising it later.

CodePudding user response：

Changing this line:

abundant = {i for i in range(1, 28124) if SumProper(i) > i}

Gives the answer you cited as correct.

The issue is an error in logic not contained in your post but implicit in the code. The problem statement is to find the sum of all positive integers not writable as the sum of two abundant numbers. You're given that all integers above N = 28123 can be written as the sum of two abundant numbers. The code then assumes this implies all integers above N = 28123 can be written as the sum of two abundant numbers, each of which is at most N/2, which is incorrect.

That said, the use of floating point division and multiplication when you're explicitly dealing with integers and divisibility seems like a recipe for disaster once your rounding errors get too large. However, those are not the cause of this bug.