Problem #23 is similar to Problem #21 in that it concerns the sum of the proper divisors of numbers as well as abundant numbers. However, Problem #21 discussed amicable numbers which pair abundant numbers with non-abundant numbers while in this question, we are mostly concerned about abundant numbers. The question reads:
Project Euler Problem 23: Non-abundant sums
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.
If you read my solution to Problem #21, you can probably guess what I plan to do for this problem. Here’s my solution:
Solution #1: Sieve Approach
In this approach, we use a Sieve-like algorithm to find all of the abundant numbers less than 28123. Then we use another Sieve-like algorithm to find all numbers which are not the sum of two abundant numbers less than or equal to 28123. Here’s an implementation of this solution in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #23
'''
import time
def projectEulerProblemTwentyThree(n):
sums = [0]*(n+1)
for i in range(2,n/2+1):
for c in range(2*i, n+1, i):
sums[c]+=i
abundant = []
for i in range(n+1):
if(sums[i]>i):
abundant.append(i)
possible = [True]*(n+1)
possible[0] = False
for a in abundant:
for b in abundant:
if(b>a or (a+b) > n):
break
possible[a+b] = False
total = 0
for i in range(n+1):
if(possible[i]):
total+=i
return total
start = time.time()
print projectEulerProblemTwentyThree(28123)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
4179871
--- 0.863159894943 seconds ---
for input of n=28123
'''
This solution is relatively inefficient as it takes almost a second to run even for small inputs such as 28123. I’d like to return to this question eventually to further optimize this solution.
Thanks for reading!
The Inner Machinations of Walker 