Project Euler Problem 23 Solution

Project Euler & HackerRank Problem 23 Solution

Non–abundant sums
by {BetaProjects} | APRIL 9, 2009 | Project Euler & HackerRank

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 stated that all natural numbers greater than 28123 can be derived as a sum of two abundant numbers. But for numbers less than 28123 there are some exceptions. We are asked to find those exceptions and sum them 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.”

So our upper bound is lowered from 28123 to 20162.

Searching the range

As this problem is an investigative endeavor, it can be solved by building a set of target numbers that can’t be formed from the sum of two abundant numbers. Also, keep in mind that the two abundant number can be the same, such as 12+12=24. This excludes 24 from our target list.

Following the algorithm

Let’s look at the process of building a set of abundant numbers and then determining which ones cannot be represented by adding two abundant numbers together (marked with an asterisk*).

abn = set()
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 are also abundant.

The any function is used to make 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 processed as:

The Python built–in function any() is like a series of logical or operators and processing stops and returns true as soon as one condition is met.

HackerRank version

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

Last Word