Project Euler 23: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Problem 23 of Project Euler is about factorisation of a number once again, and has a rather long description. So let me give that to you right away

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.

I have only found one effective approach for this problem in C#, there might be more but I haven’t found them. My approach can be summaries in three steps

  1. Find all abundant numbers
  2. Create and mark all number which can be created as the sum of two abundant numbers
  3. Sum up all non-marked numbers

Finding the abundant numbers

In the solution of Problem 21 we spent a lot of time on developing an algorithm that can effectively calculate the sum of factors.  So I will reuse that, and then it becomes trivial to calculate all the abundant numbers. I have use a code snippet in C# that looks like

const int limit = 28123;
List<int> abundent = new List<int>();
int[] primelist = ESieve((int)Math.Sqrt(limit));

// Find all abundant numbers
for (int i = 2; i <= limit; i++) {
    if (sumOfFactorsPrime(i, primelist) > i) {
        abundent.Add(i);
    }
}

Create all sums of numbers

I have done this step by creating two nested for loops, where the outer runs through all the found abundant numbers, and the inner loop runs through all abundant numbers equal to or larger than the current position of the outer loop.

One little trick. We already know that all numbers above 28123 can be written as a sum of two abundant numbers, and we also know that the list is sorted ascendantly. So as soon as we reach a sum which is above 28123, we can break out of the inner loop.

For marking purpose I have chosen a bool array to mark the numbers which can be written as abundant numbers. The C# code for it looks as

// Make all the sums of two abundant numbers
bool[] canBeWrittenasAbundent = new bool[limit + 1];
for (int i = 0; i < abundent.Count; i++) {
    for (int j = i; j < abundent.Count; j++) {
        if (abundent[i] + abundent[j] <= limit) {
            canBeWrittenasAbundent[abundent[i] + abundent[j]] = true;
        } else {
            break;
        }
    }
}

Summing up

Now we have a list of all the numbers below our limit that can and cannot be written as a sum of two abundant numbers. So now the only thing left is to sum it up.

//Sum the numbers which are not sums of two abundant numbers
for (int i = 1; i <= limit; i++) {
    if (!canBeWrittenasAbundent[i]) {
        sum += i;
    }
}

Closing remarks

I went through the 3 steps on how to do it. The result of the code is

The sum of all numbers that cannot be written as the sum of two abundant numbers is 4179871
Solution took 110 ms

As usual you are welcome to study the source code.

It uses 110ms, so it is not the fastest code in the world, but still well within the limit of 1 minute execution time. A bit of research leads to the abundant number article on Wolfram, which states that all numbers above 20161 can be written as a sum of two abundant numbers. They don’t state a source, but the result of running this code is the same if we tighten the bound.

I think this problem was fun to solve. Unlike some problems, once you have solved this one, there is nothing much to study. So it is time to move on to the next exercise.

Posted by Kristian

22 comments

[…] Prob23.cpp : Defines the entry point for the console application. // //http://www.mathblog.dk/project-euler-23-find-positive-integers-not-sum-of-abundant-numbers/ //http://mathworld.wolfram.com/AbundantNumber.html […]

The outer loop should break when abundant[i]>limit/2

I used the exactly same logic in my c++ program
But it takes hours to execute
What must be the reason behind this?

I don’t know why yours would be so slow compared to mine. My guess would be some kind of bug. After all I don’t have that fast a computer.

Also would you care to explain why the outer loop should break at that point?

In summing aal numbers
When i>limit
j is also >limit and the sum abundent[i]+abundent[j] is always greater than
limit
So outer loop should break
My programme was slow because I had added a cout in inner loop to keep track of where my program reached
i removed this statement and running time of my programm decreased from hours to a few seconds
Thanks for your reply

I see your point now, and you are absolutely right. It can be terminated at the limit you are stating. Thanks for that insight.

Oh the classical writing outputs in the inner loop. I don’t think I can count how many times I have done that and wondered why the performance was so slow.

/Kristian

You could also use the fact that every multiple of an abundant number is an abundant number.

Interesting fact, I didn’t know that. I am very uncertain how I would use that fact though. Checking if the number is a multiple of any number already found seems to be almost as costly as just doing the factorization again. I would love to hear if and how you have used this fact to solve the problem.

I used a boolean array instead of a list to store the abundant numbers. That way, just mark indexes of n, 2n, 3n and so on in the array. Basically:


for (i = 12; i < MAX; i++)
{
if (!abundants[i] && isAbundant(i))
{
for (j = i; j < MAX; j += j) /* all multiples of abundant numbers are abundant */
{
abundants[j] = true;
}
}
}

Ah cool. Do you notice any difference in speed by doing it that way?

Not much actually 🙂

I checked again, and the list version is actually faster. Maybe there is a smarter and more efficient way to use that fact..

I had a feeling that it wouldn’t. However, not matter what this fact is interesting. I can prove that the double of an abundant number is also abundant, but I can’t quite do it when I mulitply by 3. I guess I will have to reach for pen and paper again.

The middle step you have there, where you calculate all the sums…the same logic written in tcl takes a while on my computer. OK, my computer’s slow, and tcl is not the quickest either but most of the Euler problems I can solve in under 1 second. But that nested loop takes about 25 seconds to run, which is a little long for my liking. The way I figure it, there’s ~7000 abundant numbers under 28,123 and this works out to around 18 million combinations that need to be checked. And only 25,000 or so of those combinations are needed, so it seems like overkill.

What I do instead is first find all the abundants, and then I have one final loop to check every number n from 1 to 28123. This loop has an inner loop where I go through a sorted list of the abundant numbers I found. I subtract each abundant number from n and check whether the difference is an abundant number.

This method gives me the answer a lot quicker, in 4 seconds, which is still quite long (it does 4.5 million subtraction calculations), but it’s a big improvement.

Got in under 1 second now. Same approach as before, but in the first step I now split the abundant numbers into two groups: even abundants and odd abundants. Why? There are only 62 odd abundant numbers that are less than 28123. The lowest odd abundant number is 915.

So in the final loop, where I check each number to see if it is a sum, I check the odd numbers and the even numbers separately. For every odd number n, I only need to subtract every odd abundant number less than or equal to n and see if the difference is an even abundant. For even numbers, I need two checks, one subtracting even abundants to see if the difference is also an even abundant, and the same for odd abundants.

This reduces the number of subtractions needed from 4.5 million to 100 thousand, but it does make for some ugly looking code.

Ljubisa Cvetic

Lou Weed, the lowest odd abundant number is 945, not 915.
945 = 3^3 * 5 * 7, smallest odd abundant number (divisors less than itself add up to 975); smallest odd primitive abundant number; smallest odd primitive semiperfect number; Leyland number.
http://en.wikipedia.org/wiki/945_(number)

There’s another really useful fact.
Every even number above 46 can be expressed as the sum of two abundant numbers in atleast one way.
So that is going to help like crazy 😀
Here’s a link to the proof.
http://oeis.org/wiki/Abundant_numbers#Properties

http://codepad.org/tRvHw6J2

I have done the same code in c++.
Why is that giving me a wrong answer?

Jean-Marie Hachey

Table 1
Integers that are not the sum of two abundant numbers
(not necessarily distinct).
[Re: Project Euler – Problem 23]

http://img15.hostingpics.net/pics/409233pe23tab1instan.jpg

___

Sources:
1) PE23, Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem23.cs
2) Microsoft Visual C# 2010 Express
3) Abundant numbers (sum of divisors of n exceeds 2n).
http://oeis.org/A005101
4) Numbers that are not the sum of two abundant numbers (not necessarily distinct).
http://oeis.org/A048242
5) Microsoft Office Excel (2007)

I programmed my solution using a method similar to Lou’s in Java. It took hours. Thanks for the direction, using the boolean array saves the hustle of checking every number to the MAX.

Carl Appellof

While populating the bool array of sums of abundants, I noticed I was marking the same element a lot more than once. For instance 18 + 18 == 12 + 24. There must be some way of avoiding all these redundant calculations.

BTW, in C++, it took my laptop just 23ms from start to finish. But running the same code compiled for debug took 25.5 SECONDS. Let’s hear it for optimizing compilers!

noah overcash

Very helpful, thanks! I wrote this in PHP, and was checking the entire array for each sum on each loop. Wasn’t even 20% done in an hour. However, the use of a boolean array really helped!!

Here is mine: https://github.com/smileytechguy/sample_projects/blob/master/non_abundant_sums/php/non_abundant_sums.php

Leave a Reply