Problem 23: Non-abundant sums
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.
Algorthim:
I never really got around this problem. Solved this fairly recently. So, we have three steps
-
First, find the sum of all proper divisors up to 28123
-
This is an updated version of divisor sum. Instead of using the formula
given in Problem 21, we add each multiple of the
dummy variable in the for loop to a given array index (val, in this case).
I think it's easier to show in a gif:
-
See for example, we start with an array thats filled with ones.
Since every number is divisible by 1. Then we start with two. Any index
that is divisible by 2 will have to have the two included in the sum. Hence,
We can do this again for the next integer: 3
-
See for example, we start with an array thats filled with ones.
Since every number is divisible by 1. Then we start with two. Any index
that is divisible by 2 will have to have the two included in the sum. Hence,
-
This is an updated version of divisor sum. Instead of using the formula
given in Problem 21, we add each multiple of the
dummy variable in the for loop to a given array index (val, in this case).
I think it's easier to show in a gif:
- Second, we have to subtract each divisor sum by the number since we want proper divisors
- Then, we pickout abundant numbers, so go through the list and check if d(n) > n
- Lastly, we create a matrix filled with zeroes (ab matrix) and allow the index to be the sum of two abundant numbers. We go through two for loops (since we need a sum),letting ab[sum of two abundant numbers] = 1. We can check which index contains a 0. And we just sum up all the indices that contain a 0!
Code:
Result:
Answer: 4179871
Runtime: 8.8 seconds