programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Junilu Lacar
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Rob Spoor
• Bear Bibeault
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Piet Souris
• Carey Brown
• Stephan van Hulst
Bartenders:
• Frits Walraven
• fred rosenberger
• salvin francis

# Project Euler: Problem 23

Ranch Hand
Posts: 808
• Number of slices to send:
Optional 'thank-you' note:
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?

lowercase baba
Posts: 12992
66
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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.

Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:

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
Posts: 12992
66
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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!

Bartender
Posts: 1204
22
• Number of slices to send:
Optional 'thank-you' note:

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 Vashko
Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:

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.

 Get meta with me! What pursues us is our own obsessions! But not this tiny ad: Thread Boost feature https://coderanch.com/t/674455/Thread-Boost-feature