I'm working on Project Euler #23 and for the first time so far, I'm really confused, and the more I Google, the more confused I get.
The problem states:
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.
My initial algorithm is...
- Calculate all abundant numbers (<= 28123).
- Calculate all numbers that can be written as the sum of two abundant numbers. (Brute force style - with a nested loop, literally adding every possible combination of the calculated abundant numbers and inserting the sums into an array).
- Determine all numbers (<= 28123) that do not appear in the generated array of sums.
This seemed like a sound approach - it's basically the same one Kristian at Mathblog outlined, but it's not only super inefficient with significantly longer run time than all my previous solutions, but it also gave me the wrong output.
I didn't fully understand Kristian's code because a, I don's speak C, and b the dude is summing the factors of prime numbers in his first code block...? What the actual heck is going on here? What do primes have to do with it?
Seeking further clarification I ran into this article which casually states:
All highly composite numbers or anti-primes greater than six are abundant numbers.
However, the linked Wikipedia article lists 7 thru 11 as "highly composite numbers" and I know that 12 is the smallest abundant number, so there's no possible way the above statement could be accurate... right?
I'm not looking for code, just an efficient, understandable algorithm in plain English. I'm also not a Math person so please try to use small words if you can. I just need to understand that secret prime number sauce Kristian used so I can implement it. I need that voodoo magic from the number gods explained in a way I can understand it.
Your time is very much appreciated.