dennis deems

Ranch Hand

Posts: 808

posted 5 years ago

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?

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?

posted 5 years ago

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.

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

dennis deems

Ranch Hand

Posts: 808

posted 5 years ago

Same.

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.

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.

posted 5 years ago

Exactly.

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

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

dennis deems

Ranch Hand

Posts: 808

posted 5 years ago

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: 1113

7

posted 5 years ago

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 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?)

posted 5 years ago

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

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.

Consider Paul's rocket mass heater. |