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)|
    .take_while { |i| (n+i) <= 28123 }.map { |i| n+i }

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

solution_set = (1..28123).set - inverse_set


▸ 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.

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

1 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
  • \$\begingroup\$ Why not reduce(:+)? \$\endgroup\$
    – Nakilon
    Commented Apr 5, 2013 at 11:38
  • \$\begingroup\$ @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 :-) \$\endgroup\$
    – tokland
    Commented Apr 5, 2013 at 12:08
  • 1
    \$\begingroup\$ This is about 1 second faster than mine, but yay!, readability counts :). \$\endgroup\$
    – ichigolas
    Commented Apr 5, 2013 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.