Project Euler Problem 23 Solution: Non-abundant sums

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 finite 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 and are added to our noSum[] list.

abundant = set()
n                                n
1	abundant([])         *    |   21	abundant([20,18,12])               *
2	abundant([])         *    |   22	abundant([20,18,12])               *
3	abundant([])         *    |   23	abundant([20,18,12])               *
4	abundant([])         *    |   24	abundant([24,20,18,12])          12+12
5	abundant([])         *    |   25	abundant([24,20,18,12])            *
6	abundant([])         *    |   26	abundant([24,20,18,12])            *
7	abundant([])         *    |   27	abundant([24,20,18,12])            *
8	abundant([])         *    |   28	abundant([24,20,18,12])            *
9	abundant([])         *    |   29	abundant([24,20,18,12])            *
10	abundant([])         *    |   30	abundant([24,20,18,12,30])       18+12
11	abundant([])         *    |   31	abundant([24,20,18,12,30])         *
12	abundant([12])       *    |   32	abundant([24,20,18,12,30])	    20+12
13	abundant([12])       *    |   33	abundant([24,20,18,12,30])         *
14	abundant([12])       *    |   34	abundant([24,20,18,12,30])         *
15	abundant([12])       *    |   35	abundant([24,20,18,12,30])         *
16	abundant([12])       *    |   36	abundant([36,12,18,20,24,30])    12+24
17	abundant([12])       *    |   37	abundant([36,12,18,20,24,30])      *
18	abundant([18,12])    *    |   38	abundant([36,12,18,20,24,30])    18+20
19	abundant([18,12])    *    |   39	abundant([36,12,18,20,24,30])      *
20	abundant([20,18,12]) *    |   40	abundant([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, abundant[]. 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 performs the necessary comparisons by subtracting each abundant number from the target number and checking whether the result is also 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 returns True if any item in an iterable are true, otherwise it returns False.

HackerRank version

Solves all test cases for Hackerrank 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. It requires some simple additions to cache the vales of n and handle the input.

Python Source Code

import math
L, abundant, noSum = 20162, set(), []
ds = [1]*L

for i in range(2, math.isqrt(L)): ds[i*i]+= i  # Include squares
for i in range(2, math.isqrt(L)):
    for j in range(i+1, L//i):
        ds[i*j]+= i+j
for n in range(1, L):
    if ds[n] > n: abundant.add(n)
    if not any( (n-a in abundant) for a in abundant ): noSum.append(n)
 
for _ in range(int(input())):
    print("NO" if int(input()) in noSum else "YES")

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).
There is a great discussion of how the sum of proper divisors is calculated here: Sieve Method for Finding Sum of Proper Divisors