Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithm
python

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

Educative Answers Team

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 1212 because its proper divisors add up to a number that is larger than itself, 1616 (1+2+3+4+6)(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.

svg viewer

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, nn, between 1212 and 128123128123. If nn 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 2812328123. Naturally, every number that is not in our list of abundant number sums, and is smaller than 2812328123, 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, nn, between 1212 and 128123128123. If nn is smaller than the sum of its divisors, it is an abundant number.

Next, we check every number between 11 and 128123128123. 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:
            abundantSums.add(abSum)

# 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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring