What are non-abundant sums (Euler problem 23)?

Non-abundant sums are sums of numbers that cannot be written as the sum of two abundant numbers. Abundant numbers are numbers whose sum of proper divisors is greater than the number itself. The smallest abundant number is $12$ because its proper divisors add up to a number that is larger than itself, $16$ $(1 + 2 + 3 + 4 + 6)$.

There are two types of non-abundant numbers: perfect numbers and deficient numbers. A perfect number is a number whose sum of proper divisors is equal to the number itself. A deficient number is a number whose sum of proper divisors is less than the number itself.

Euler’s problem 23 asks us to calculate the sum of all the positive integers that cannot be written as the sum of two abundant numbers. It states:

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. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers that cannot be written as the sum of two abundant numbers.

Implementation

There are many ways you can go about it. Let’s look at two:

Python

We first construct a list of abundant numbers by checking each number, $n$, between $12$ and $128123$. If $n$ is smaller than the sum of its divisors, it is an abundant number.

After we have our abundant numbers, we use them to calculate a list of abundant number sums less than or equal to $28123$. Naturally, every number that is not in our list of abundant number sums, and is smaller than $28123$, is not an abundant number sum. This is the logic behind our third and final list, non-abundant sums.

Finally, we return the sum of all the numbers in this list for our answer.

C++

We first construct a list of abundant numbers by checking each number, $n$, between $12$ and $128123$. If $n$ is smaller than the sum of its divisors, it is an abundant number.

Next, we check every number between $1$ and $128123$. If they’re NOT abundant numbers, we accumulate them in our sum variable.