Here’s problem twenty three:

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

This problem was rather complicated…it took me a while to come up with an efficient way of solving it. Bits of this code are actually the result of reading other people’s solutions to improve my own.

Take a look:

def abundantNumberGen(limit): # returns list of abundant numbers up to limit
numbers = []
for x in range(1, limit):
if sum(properFactors(x)) > x:
numbers.append(x)
return numbers
def properFactors(n): # returns list of proper factors of a number
factors = [1] # 1 is automatically a factor
for x in range(2, int(n**0.5)+1):
if n % x == 0:
factors.extend([x, n/x])
if n**0.5 == int(n**0.5): # important! must remove the extra square root if n is a perfect square
factors.remove(n**0.5)
return factors
result = list(range(28123)) # list of numbers up to 28123; result[12] = 12, result[28122] = 28122
abundantNumbers = abundantNumberGen(28123)
for n in abundantNumbers:
for m in abundantNumbers:
if n + m < 28123:
result[n + m] = 0 # result[100] = 100 --> result[100] = 0
print(sum(result))

Instead of directly reading the run code first, let’s analyze the functions first for a change of pace.

def properFactors(n): # returns list of proper factors of a number
factors = [1] # 1 is automatically a factor
for x in range(2, int(n**0.5)+1):
if n % x == 0:
factors.extend([x, n/x])
if n**0.5 == int(n**0.5): # important! must remove the extra square root if n is a perfect square
factors.remove(n**0.5)
return factors

This function is used repeatedly in calculating the solution, so any increase in efficiency here would significantly reduce the run time overall. This was done by automatically setting one as a factor, and only test-dividing up to the square root of the number. The factors found are stored in a list, and every time we find a factor, we add its corresponding factors (e.g. the number is 10, we find 2 and then find 5) to the list. It’s extremely important to remove the duplicate square root factor if the number is a perfect square; I initially overlooked this fact and ended up with a wrong answer. This is a more general version of the *D(n)* function used in problem 21.

def abundantNumberGen(limit): # returns list of abundant numbers up to limit
numbers = []
for x in range(1, limit):
if sum(properFactors(x)) > x:
numbers.append(x)
return numbers

This function returns a list abundant numbers up to a specified limit, directly using the definition of an abundant number. We test if the sum of a number’s proper divisors is greater than the number itself, and if true, we append it to the list.

result = list(range(28123)) # list of numbers up to 28123; result[12] = 12, result[28122] = 28122
abundantNumbers = abundantNumberGen(28123)
for n in abundantNumbers:
for m in abundantNumbers:
if n + m < 28123:
result[n + m] = 0 # result[100] = 100 --> result[100] = 0
print(sum(result))

Now let’s look at the run code. The first line here was adapted from another solution I found, since I thought it was an extremely clever and efficient way of tackling this problem. Line 1 creates a list where the elements are equal to their indexes, i.e. *list[10] = 10, list[124] = 124*, simple but very useful. We generate abundant numbers up to the specified limit of 28123 (because we want a sum of abundant numbers that is less than 28123). We then test every combination of two abundant numbers, using two for loops, and if the result is less than 28123, i.e. a number that can be expressed as the sum of two abundant numbers, we set that element of the list to zero. When this finishes, all the numbers in the list that can be expressed as a sum of abundant numbers will be zero, and we can simply sum the remaining to find the solution.

*Answer: 4179871*

Tags: abundant number, proper factor