Project Euler: Problem 23
dennis deems
Ranch Hand
Posts: 808
posted 4 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 bruteforce 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 onthefly. 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 bruteforce 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 onthefly. 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 4 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 offbyone errors
dennis deems
Ranch Hand
Posts: 808
posted 4 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 4 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 4 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 lessthanorequals where simple lessthan suffices. I'm a little sad I couldn't do better but I don't think I am in the mood for ferreting out microoptimizations. Thanks again!
Ryan McGuire
Ranch Hand
Posts: 1108
7
posted 4 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 4 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.
Gravity is a harsh mistress. But this tiny ad is pretty easy to deal with:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
