Project Euler #23 - Python Non Abundant Sums

Question

I have been working on Project Euler #23.

This is the task:

Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis >even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

This is my code:

import math

def getDivisors(num):
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    return total

def isAbundant(num):
    if (getDivisors(num) > num):
        return True
    else:
        return False

abundentNums = []
for x in range (0,28124):
    if (isAbundant(x)):
        abundentNums.append(x)
del abundentNums[0]

sums = [0]*28124
for x in range (0, len(abundentNums)):
    for y in range (x, len(abundentNums)):
            sumOf2AbundantNums = abundentNums[x]+abundentNums[y]
            if (sumOf2AbundantNums<= 28123):
                if (sums[sumOf2AbundantNums] == 0):
                    sums[sumOf2AbundantNums] = sumOf2AbundantNums

total = 0
for x in range (1,len(sums)):
    if (sums[x] == 0):
        total +=x

print('\n', total)

The total value I get is 4190404. The correct answer is 4179871.I have spent an hour looking at my code, but I am unable to find the error. What should I change to correct the error? My answer is close. Thanks in advance

PS. I am new to python. Run time is 25s any optimisations will be useful as well.

Answer 1

Your getDivisors function is incorrect. It doesn't count the root divisors of square numbers (for example, if num=25, it will return 1). Here is a corrected version:

def getDivisors(num):
    if num==1:
        return 1
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    if n**2==num:
        total+=n
    return total

with this function I get the required result 4179871.

Answer 2

This code works 6 seconds on my computer:

from math import sqrt
import itertools
import functools
import operator
#simplicity test
def fuc(a):
    d = 1
    z = 0
    while d<= sqrt(a):
        d = d + 1
        if a == 2:
            z = a
        elif (a%d) == 0:
            z = False
            break

        else:
            z = a
    return z
#prime number divisors
def func(value):
    v = []
    d = 1
    value1= value# for optimization
    while d <= sqrt(value1):
        d+=1
        if fuc(d)!= False and value1 % d == 0:
            v.append(d)
            value1 = value1/d
            d = 1
    if value1 != value and value1 != 1:
        v.append(value1)
    return v
# all number divisors without 1 and source number
def calculate_devisors(n):
    prime_multiples_list = func(n)
    unique_combinations = set()
    for i in range(1, len(prime_multiples_list)):
        unique_combinations.update(set(itertools.combinations(prime_multiples_list,i)))
        combinations_product = list(functools.reduce(operator.mul,i) for i in unique_combinations)
        combinations_product.sort()
    try:
        return combinations_product
    except:
        return []

abundentNums = []

for n in range(1,28123):
    if sum(calculate_devisors(n))+1>n:
        abundentNums.append(n)

sums = [0]*28124
for x in range (0, len(abundentNums)):
    for y in range (x, len(abundentNums)):
        sumOf2AbundantNums = abundentNums[x]+abundentNums[y]
        if (sumOf2AbundantNums<= 28123):
            if (sums[sumOf2AbundantNums] == 0):
                sums[sumOf2AbundantNums] = sumOf2AbundantNums
ans = 0
for i in range(1,len(sums)):
    if sums[i]==0:
        ans+=i
print(ans)