Optimizing code for Project-Euler Problem #23

Question

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.

• Nakilon: Why to optimize the PE solution, which finishes in the slowest language in far less, than a minute?
• ichigolas: Holy sh#t. Upgrading to ruby 2 got execution time down to 7 secs.

Answer 1

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

• Nakilon: Why not reduce(:+)?
• tokland: @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 :-)
• ichigolas: This is about 1 second faster than mine, but yay!, readability counts :).