Problem 23: Non-abundant sums

*Difficulty: Easy

Problem:

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 n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

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 which cannot be written as the sum of two abundant numbers.

How to solve:

From the description above, sum of all the positive integer which cannot be written as the sum of two abundant numbers = sum of all positive integer smaller than 28124 that cannot be created by sum of two abundant numbers.

To do this we need to do three thing

  1. create an abundant numbers list
  2. go through that list, calculate the sum of two abundant number, make sure the sum is smaller than 28124, mark it as a number that can be constructed by the sum of two abundant number.
  3. go through the list from 1 to 28123, if it is not marked, then it is non-abundant sum number.

In order to create an abundant numbers list, we must have a method to calculate the sum divisors (proper divisors) of a number, I know three ways to do this, I will show you two out of three ways, the last one is using prime factorization, it’s a little bit complicated.

Here is the first one, also the easiest one, go through from 1 to n-1, check if n mod i ==0, count it to sum

Screen Shot 2016-07-01 at 12.18.15 AM

The second one is a bit more tricky, as you may know, we just need to loop to square root of n to calculate its sum of divisors, but we need its sum of proper divisors. Hence, before we return the value, we must subtract it from n itself (sum-n)

Screen Shot 2016-07-01 at 12.20.47 AM

Create an abundant numbers list

Screen Shot 2016-07-01 at 12.21.59 AM

go through the list and mark as described above

Screen Shot 2016-07-01 at 12.22.57 AM

go through the list, sum up all the values that is not marked

Screen Shot 2016-07-01 at 12.24.14 AM

Solution took 384 ms

Advertisements