Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# Project Euler: Problem 23

dennis deems
Ranch Hand
Posts: 808
http://projecteuler.net/problem=23

As always, please don't post a solution. The problem is: "Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers." For free they give you the upper bound of this set of numbers as 28123. However, even when I limit my search to integers under 5000, it takes over a minute to return a result. I am using a brute-force approach, first finding all the abundant numbers below 28123, then iterating over all positive integers below the limit to see if they can be a sum of two abundant numbers. My algorithm for that test is:

I thought it would be better to establish the set of known abundant numbers first, and that checking to see if the difference is contained in that list would be more efficient than performing the test for abundance on-the-fly. Is this assumption misguided? It's going to take at least 5 minutes to find a solution with this method. So there's got to be a better way.
Is there some trick to these numbers that I need to discover?

fred rosenberger
lowercase baba
Bartender
Posts: 12086
29
My code takes (about) 2 seconds to compute which numbers below 28123 are abundant. It then speeds through the computation in about another 2 seconds. looking at it, I could make it slightly more efficient by skipping some computations.

My suggestion would be to see where your code is taking so much time...does it take most of its time to find which numbers are abundant, or most to compute the sum? Once you know where you are spending the time, you know where to focus your time to make improvements.

dennis deems
Ranch Hand
Posts: 808
fred rosenberger wrote:My code takes (about) 2 seconds to compute which numbers below 28123 are abundant.

Same.

It then speeds through the computation in about another 2 seconds.

It takes my code just over a second to find 265 numbers that can't be the sum of abundant numbers looking in the first 500.
It takes almost 5 seconds to find 505 numbers that can't be the sum of abundant numbers looking in the first 1000.
I'm not sure why it takes four times longer to look in 1000 numbers than 500, except that their values are larger, so we're looking at more possible addends.

There's got to be a shortcut I don't see.

Martin Vajsar
Sheriff
Posts: 3751
62
Dennis Deems wrote:I'm not sure why it takes four times longer to look in 1000 numbers than 500, except that their values are larger, so we're looking at more possible addends.

Exactly.

Dennis Deems wrote:There's got to be a shortcut I don't see.

In your current approach, you're iterating over numbers and trying to see whether they can be expressed as abundant numbers. It means that all the abundant numbers are touched many many times. You might try to "reverse" the processing, so that you don't touch individual abundant numbers so many times. I used such approach and got under one second overall.

I know this sounds mysterious, but I'm trying not to tell too much at this moment...

fred rosenberger
lowercase baba
Bartender
Posts: 12086
29
That's a good hint...I was trying to come up with a way of explaining what I did without giving it away.

dennis deems
Ranch Hand
Posts: 808
Thank you both! I was surprised how much a difference it made to go at the problem from the "opposite direction". I got my execution time down to about 6 seconds. Then I shaved off half a second by realizing I was needlessly using less-than-or-equals where simple less-than suffices. I'm a little sad I couldn't do better but I don't think I am in the mood for ferreting out micro-optimizations. Thanks again!

Ryan McGuire
Ranch Hand
Posts: 1055
4
Martin Vajsar wrote:In your current approach, you're iterating over numbers and trying to see whether they can be expressed as abundant numbers. It means that all the abundant numbers are touched many many times. You might try to "reverse" the processing, so that you don't touch individual abundant numbers so many times. I used such approach and got under one second overall.

I'm using two data structures in parallel that show which numbers are abundant: an ArrayList of integers and an array of booleans. I use the ArrayList to find only abundant numbers to use as the first addend (12, 18, 20, 24, ...). Then I use the array of booleans to see if the other addend I need is also abundant. This is about twice as fast as looping through all indexes of an array of boolean looking for TRUEs to get the first addend and then accessing a boolean array element is a lot faster than checking to see if a given integer is in the ArrayList.

(Just to verify... does the final answer end in 871?)

Martin Vajsar
Sheriff
Posts: 3751
62
Ryan McGuire wrote:(Just to verify... does the final answer end in 871?)

Well, it does, but you can easily verify your answer after registering at Project Euler.