Non-abundant sums
Problem 23
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.
(
https://projecteuler.net/problem=23)
A few days ago, we had a discussion about amicable numbers.
And I mentioned about 6, which was "amicable" to itself, and now it appears again.
As the problem explains, s(6) = 1 + 2 + 3 = 6, which means it is "amicable" number to itself, or we mathematically call it a
perfect number.
Numbers like 12, where s(12) = 1 + 2 + 3 + 4 + 6 = 16 > 12, is called an
abundant number.
Personally this problem was one of some tedious problems in Project Euler.
I couldn't come up with an efficient algorithm (even though I met the Project Euler standard efficiency: 1 minute), so I ended up using sieve, reducing redundancies, and half-cutting the limit in order to meet my personal premise in problem-solving (under 1 second).
Here is my algorithm.
The problem hints us that the limit is 28123, and that the smallest abundant number is 12, and therefore the
sum of two abundant numbers is 24.
From now on, I will just call such integers that is the sum of two abundant numbers
abby numbers.
(for convenience)
(This term is not a defined mathematical term, so don't use it anywhere else.)
We are going to find the sum of non-abby numbers.
Here is my algorithm for abundant number sieve:
public static boolean[] sieveAbundance(int limit)
{
boolean[] abun = new boolean[limit + 1];
for (int i = 12; i <= limit; i++)
{
if (!abun[i])
{
if (abun[i] = isAbundant(i))
{
for (int j = i; j <= limit; j += i)
abun[j] = true;
}
}
}
return abun;
}
Overall similar principle to Sieve of Eratosthenes (problem 10), yet I have one thing to point out.
Once the number is proven to be an abundant number, then its multiples are all abundant numbers.
The proof is simple. If the sum of the proper divisors of a certain number is already greater than itself, then doubling the number will produce twice as much proper divisors for the number (and the sum of the values will definitely exceeds the original number), and the number will clearly be an abundant number.
Next, we need to determine if the number is an abundant number.
public static boolean isAbundant(int n)
{
int original = n;
int sum = 1;
if (n % 2 == 0)
{
int temp = 1;
for (int mult = 2; n % 2 == 0; n /= 2, mult *= 2)
temp += mult;
sum *= temp;
}
for (int i = 3, end = (int)Math.sqrt(n); i <= end; i += 2)
{
if (n % i == 0)
{
int temp = 1;
for (int mult = i; n % i == 0; n /= i, mult *= i)
temp += mult;
sum *= temp;
end = (int)Math.sqrt(n);
}
}
if (n != 1) sum *= 1 + n;
return original + original < sum;
}
In this algorithm, I divided the division part into [2] and [odd numbers].
(By checking the divisibility by 2, I can skip rest of even numbers.)
And the logic behind the algorithm is written here:
Let's say our number is 36. Its proper divisors are 1, 2, 3, 4, 6, 9, 12, 18.
The sum is 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 = 55 > 36. It is an abundant number.
Prime factorization: 36 = 2
2 x 3
2.
With 2
2, we can produce 1, 2, and 4. Let's add them up. 1 + 2 + 4 = 7.
Now, we have 3
2. We can produce 1, 3, and 9. Let's add them up. 1 + 3 + 9 = 13.
Let's multiply those two sums. 7 * 13 = 91.
91 minus the original number 36 equals 91 - 36 = 55. The sum of the proper divisors.
What?! How could that happen??
Ok, here is the proof.
| 36 |
20 (A) |
21 (B) |
22 (C) |
| 30 (D) |
1 |
2 |
4 |
| 31 (E) |
3 |
6 |
12 |
| 32 (F) |
9 |
18 |
36 |
where each un-bolded numbers in the table is the multiplication of two elements.
For example, 18 in the box is the product of 2
1 x 3
2, or column x row.
Instead of adding all the element manually, we are going to use
multiplication of polynomials in order to quickly get the sum of the factors. (including itself)
We want to get
AD + AE + AF + BD + BE + BF + CD + CE + CF, which we can factor out into
(A + B + C)(D + E + F). And this is (1 + 2 + 4)(1 + 3 + 9) = 91, which I did above.
Because this is the sum of every factor, we need to subtract the original number in order to get the sum of the proper factors.
Last step is to find
abby number from the information on abundant numbers we calculated.
Because it tends to have abundant numbers in bigger numbers than small numbers, the algorithm will start finding the abundant pairs from the biggest to smallest. For example, if we want to check if 72 is abby number, we will divide it into half and start with (36, 36) pair, which is more likely than (1, 71) pair.
public static boolean isSumOfTwoAbundant(int n)
{
for (int i = n / 2; i >= 12; i--)
if (isAbundant[i] && isAbundant[n - i]) return true;
return false;
}
and WE ARE FINALLY DONE!
int sum = 0;
for (int i = 1; i <= LIMIT; i++)
{
if (!isSumOfTwoAbundant(i)) sum += i;
}
System.out.println(sum);
Answer is 4179871
Execution time is 28.948803 ms
Source Code:
https://github.com/Ainodyne/Project-Euler/blob/master/Problem023.java
