Project Euler Problem 23 Solution

Project Euler Problem 23 Solution

Non-abundant sums

by {BetaProjects} | 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 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:

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

HackerRank logo

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, abn, s = 20162, set(), 0
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: abn.add(n)
    if not any( (n-a in abn) for a in abn ): s+= n

print ("The sum of all the positive integers which cannot be written as the sum of two abundant numbers",s)

Last Word