Project Euler 23 Problem 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.

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 lowered from 28123 to 20161.

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 of exceptions.

Following the algorithm

Let’s look at the process of building a set of abundant numbers. Then we’ll check which target numbers cannot be represented by adding two abundant numbers together (marked with an asterisk (‘*’)).

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

We consider each target number and, using the d() function, check if it is an abundant number. If it is, then it’s added to our set of abundant numbers, abn.

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:

  • 30-24=6, 6 is not in our set and therefore not an abundant number
  • 30-20=10, 10 is not in our set and therefore not an abundant number
  • 30-18=12 12 is in our set and therefore an abundant number. So 30 can be formed by the addition of two abundant numbers 12+18=30.

any is like a as series of logical or operators and processing stops and returns true as soon as one condition is met.

HackerRank version

HackerRank Project Euler 23 has us query 100 numbers less than 100,000 and return “YES” or “NO” for every number that can or can not be represented by adding two abundant numbers. Any number greater than 20,161 will return “YES” and all others will be pre-calculated to a cache using this algorithm.

Python 2.7 Source

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).