Project Euler Problem 23 Statement

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 whose proper divisors are less than the number is called deficient. A number whose proper divisors exceed the number is called abundant.

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.

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

Solution

The first 23 abundant numbers are:

12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, …
Reference: The On–Line Encyclopedia of Integer Sequences (OEIS) A005101: Abundant numbers

The problem states that all natural numbers greater than 28123 can be derived by summing of two abundant numbers. But for numbers less than 28123 there are some exceptions. We need to find those exceptions and add them together for an answer.

As this is a close-ended problem, there is not much in the way of optimization for this brute–force solution.

Improving the search range

According to Wolfram Mathworld’s discussion on Abundant Numbers,

“Every number greater than 20161 can be expressed as a sum of two abundant numbers.”

We lower our upper bound to 20162.

Searching the range

As this problem is an investigative endeavor, it is solved by building a set of target numbers that can’t be formed from the sum of two (not necessarily distinct) abundant numbers.

Following the algorithm

Let’s look at the process of building a set of abundant numbers. An asterisk marks the ones that cannot be formed by adding two abundant numbers.

abn = set()
n                                n
1	abn([])         *    |   21	abn([20,18,12])               *
2	abn([])         *    |   22	abn([20,18,12])               *
3	abn([])         *    |   23	abn([20,18,12])               *
4	abn([])         *    |   24	abn([24,20,18,12])          12+12
5	abn([])         *    |   25	abn([24,20,18,12])            *
6	abn([])         *    |   26	abn([24,20,18,12])            *
7	abn([])         *    |   27	abn([24,20,18,12])            *
8	abn([])         *    |   28	abn([24,20,18,12])            *
9	abn([])         *    |   29	abn([24,20,18,12])            *
10	abn([])         *    |   30	abn([24,20,18,12,30])       18+12	
11	abn([])         *    |   31	abn([24,20,18,12,30])         *
12	abn([12])       *    |   32	abn([24,20,18,12,30])	    20+12
13	abn([12])       *    |   33	abn([24,20,18,12,30])         *
14	abn([12])       *    |   34	abn([24,20,18,12,30])         *
15	abn([12])       *    |   35	abn([24,20,18,12,30])         *
16	abn([12])       *    |   36	abn([36,12,18,20,24,30])    12+24	
17	abn([12])       *    |   37	abn([36,12,18,20,24,30])      *
18	abn([18,12])    *    |   38	abn([36,12,18,20,24,30])    18+20	
19	abn([18,12])    *    |   39	abn([36,12,18,20,24,30])      *
20	abn([20,18,12]) *    |   40	abn([36,40,12,18,20,24,30]) 20+20

We consider each target number, n, and determine if the sum of its divisors exceeds the number. If it does, then it’s added to our set of abundant numbers, abn. As an aside, once an abundant number is found, then each of its multiples is also an abundant number. For example, when we determine 12 is abundant, then 24, 36, 48, … , 12k; k>1 are also abundant.

The any function makes the necessary comparisons. It subtracts every abundant number from the target number and checks if the result is an abundant number. For example, the target number 30 is checked as:

• 30−24=6, 6 is not in our set.
• 30−20=10, 10 is not in our set.
• 30−18=12, 12 is in our set and therefore an abundant number. So, 30 can be formed by the sum of two abundant numbers and excluded from our list.

The Python function any() is a series of logical or comparisons. It only checks until the first true condition otherwise returns false.

HackerRank version

Extended to solve all test cases for Project Euler Problem 23

HackerRank Project Euler 23 simply asks for a YES/NO answer to a number being the sum of two abundant numbers. Every number greater than 20161 can be expressed as a sum of two abundant numbers so HackerRank's upper limit of 100,000 is superfluous. We pre–calculate all the results to a cache, p23[] to accommodate the 100 test case runs.

Python Source Code

 Use this link to download the Project Euler Problem 23: Non–abundant sums Python source.

 Run Project Euler Problem 23 using Python on repl.it

Last Word

• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A048242: Numbers that are not the sum of two abundant numbers (not necessarily distinct).