1
\$\begingroup\$

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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