# Optimizing code for Project-Euler Problem #23

I'm working on Project Euler's problem #23, which is

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers

I came up with this algorithm. Find all abundant numbers under 28123 (defined Numeric#abundant?), this is slow and could be faster if skipped primes, but is fairly fast (less than 4 secs):

abundant_numbers = (12..28123).select(&:abundant?)


Find all numbers that can be expressed as the sum of 2 perfect numbers:

inverse_set = abundant_numbers.each.with_index.inject([]) do |a,(n,index)|
a.concat(
abundant_numbers[index..abundant_numbers.size-1]
.take_while { |i| (n+i) <= 28123 }.map { |i| n+i }
)
end.to_set


The rest them from all the integers under 28123 and sum them all:

solution_set = (1..28123).set - inverse_set
solution_set.reduce(:+)


Benchmarked:

▸ time ruby 0023.rb
real  0m20.036s
user  0m19.593s
sys  0m0.352s
▸ rvm use 2.0.0
▸ time ruby 0023.rb
Solution: 4*****1

real  0m7.478s
user  0m7.348s
sys  0m0.108s


It works, but it's a little bit slow, takes about 20secs to solve, and I hear people around saying it can be solved within miliseconds. I'm sure many of you will have a quick insight on what have I missed.

• Why to optimize the PE solution, which finishes in the slowest language in far less, than a minute? – Nakilon Apr 5 '13 at 11:39
• Holy sh#t. Upgrading to ruby 2 got execution time down to 7 secs. – nicooga Apr 5 '13 at 14:42

Your idea is perfectly fine (subtracting all sum of pairs from the candidates range), but I would write it differently:

xs = (1..28123)
abundants = xs.select(&:abundant?)
solution = (xs.to_set - abundants.repeated_combination(2).to_set { |x, y| x + y }).sum


With a similar idea, this is probably faster (but also a bit less declarative):

xs = (1..28123)
abundants = xs.select(&:abundant?).to_set
solution = xs.select { |x| abundants.none? { |a| abundants.include?(x - a) } }.sum

• Why not reduce(:+)? – Nakilon Apr 5 '13 at 11:38
• @Nakilon: Well, it's not necessary, but it gives you one thing less to worry about (is the input empty?). It does no harm to add the identity element of the operation. Anyway, I've abstracted it as sum, problem solved :-) – tokland Apr 5 '13 at 12:08
• This is about 1 second faster than mine, but yay!, readability counts :). – nicooga Apr 5 '13 at 14:45