Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithm
python

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

# returns the sum of divisors
def is_abundant(n):
# Check if the number n is divisible by numbers from 2 to half of n
sumOfDivisors = 1 # 1 is always a proper divisor
for x in range(2, (n//2 + 1)):
if n % x == 0:
sumOfDivisors += x
return sumOfDivisors > n

# list of abundant numbers - the smallest abdundant no is 12
abundantNums = [number for number in range(12,28124) if is_abundant(number)]

# get all abundant sums less and equal to 28123
abundantSums = set([])
for numOne in abundantNums:
for numTwo in abundantNums:
abSum = numOne + numTwo
if abSum > 28123:
break
else:

# compile list of non-absolute sums
NonAbSums = [number for number in range(28124) if number not in abundantSums]

# print the sum of the non-absolute list
print(sum(NonAbSums))

RELATED TAGS

algorithm
python