Highly composite numbers and Abundant numbers

Question

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

1. Calculate all abundant numbers (<= 28123).
2. 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).
3. 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.

Answer 1

Most common method -

1. Calculate all abundant numbers (<= 28123).
2. Store them in ascending order, preferably in an array or something.
3. Now take two loops. In the first loop, start from the smallest abundant number till the last and then in the second loop, start from the previous loop variable succeeding that till the last and check if their sum is an abundant number. If yes, store them in a new array. Also, for making it work faster, you can only also use the condition that the sum of those 2 numbers (the loop variables) should be <= 28123.
4. Now see which numbers (from 1-28123) are not present in the second array. Then find their sum.

Alternative Easy Method -

Steps 1 and 2 are same.

3. Take a variable for storing sum and initialise it to 0. Take two loops. In the first loop, start from the smallest abundant number till the last one and then in the second loop, start from the previous loop variable till the last number in abundant numbers array. If the sum of the two numbers is an abundant number, then add the value of the sum to the variable.

4. Formula for sum of first 'n' natural numbers is n(n+1)/2 . So simply subtract sum from 28123*28124/2 to get your result.

Answer 2

The major difference between your algorithm and Kristian's is his use of an algorithm to calculate the sum of the factors based on prime factorization, which he describes here. I'll try to explain how this works.

We input a positive integer $n$.

The prime factorization of $n$ is a unique way of writing $n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$ for prime numbers $p_1, p_2, \dotsc, p_r$ and positive integers $e_1, e_2, \dotsc, e_r$. For example, the prime factorization of $12$ is $12 = 2^2 3^1$. Assuming we have a list of primes, we can find the prime factorization by testing if each prime divides $n$.

Once we have the prime factorization $n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$, the factors of $n$ are all integers which can be factorized as $p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r}$ with $0 \leq i_r \leq e_r$. So, in our example, the factors of $12$ are $2^0 3^0$, $2^1 3^0$, $2^2 3^0$, $2^0 3^1$, $2^1 3^1$, and $2^2 3^1$.

Now (here I deviate a bit from Kristian's explanation) if we expand the product $$ (p_1^0 + p_1^1 + \dots + p_1^{e_1}) \cdot (p_2^0 + p_2^1 + \dots + p_2^{e_2}) \cdots (p_r^0 + p_r^1 + \dots + p_r^{e_r}) $$ we get one term corresponding to each factor $p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r}$, and all the terms of are summed. This is Kristian's $t(n)$: the sum of all the factors of $n$.

Kristian shows that each term of the type $p^0 + p^1 + \dots + p^a = \frac{p^{a+1}-1}{p-1}$ as follows. Let $$T = p^0 + p^1 + \dots + p^a$$ Then $$pT = p^1 + p^2 + \dots + p^{a+1}$$ Subtracting the first equation from the second, a lot of terms cancel, and we get $$(p-1)T = p^{a+1} - p^0 = p^{a+1}-1$$ So $$T = \frac{p^{a+1}-1}{p-1}$$

This is all the information we need to find the sum of the factors. The algorithm will proceed as follows:

• Input $n$
• Find the prime factorization of $n$ as described above
• For each term $p_i^{e_i}$ in the prime factorization, compute $\frac{p_i^{e_i+1}-1}{p_i-1}$; let $t(n) = $ the product of all the $\frac{p_i^{e_i+1}-1}{p_i-1}$ terms
• The sum of the proper divisors is $t(n) - n$