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.

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