I'm working on Project Euler's problem #23, which isFind the sum of all the positive integers which cannot be written as the sum of two abundant numbersI 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_setThe rest them from all the integers under 28123 and sum them all:solution_set = (1..28123).set - inverse_setsolution_set.reduce(:+)Benchmarked: time ruby 0023.rb  real  0m20.036suser  0m19.593s sys  0m0.352s rvm use 2.0.0 time ruby 0023.rb Solution: 4*****1real  0m7.478suser  0m7.348s sys  0m0.108sIt 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.
Optimizing code for Project-Euler Problem #23
ruby;programming challenge;primes
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 }).sumWith a similar idea, this is probably faster (but also a bit less declarative):xs = (1..28123)abundants = xs.select(&:abundant?).to_setsolution = xs.select { |x| abundants.none? { |a| abundants.include?(x - a) } }.sum