Euler 23 in Ruby

Question

All right. I think I have the right idea to find the solution to Euler #23 (The one about finding the sum of all numbers that can't be expressed as the sum of two abundant numbers).

However, it is clear that one of my methods is too damn brutal. How do you un-brute force this and make it work?

sum_of_two_abunds?(num, array) is the problematic method. I've tried pre-excluding certain numbers and it's still taking forever and I'm not even sure that it's giving the right answer.

def divsum(number)
  divsum = 1
  (2..Math.sqrt(number)).each {|i| divsum += i + number/i if number % i == 0}
  divsum -= Math.sqrt(number) if Math.sqrt(number).integer?
  divsum 
end

def is_abundant?(num)
  return true if divsum(num) > num
  return false
end

def get_abundants(uptonum) 
  abundants = (12..uptonum).select {|int| is_abundant?(int)}
end

def sum_of_two_abunds?(num, array)
  #abundant, and can be made from adding two abundant numbers.
  array.each do |abun1|
    array.each do |abun2|
      current = abun1+abun2

      break if current > num
      return true if current == num
    end
  end

  return false
end

def non_abundant_sum
  ceiling = 28123
  sum = (1..23).inject(:+) + (24..ceiling).select{|i| i < 945 && i % 2 != 0}.inject(:+)
  numeri = (24..ceiling).to_a
  numeri.delete_if {|i| i < 945 && i % 2 != 0}
  numeri.delete_if {|i| i % 100 == 0}
  abundants = get_abundants(ceiling)
  numeri.each {|numerus| sum += numerus if sum_of_two_abunds?(numerus, abundants) == false}
  return sum
end


start_time = Time.now

puts non_abundant_sum

#Not enough numbers getting excluded from the total. 
duration = Time.now - start_time

puts "Took #{duration} s "

Answer 1

Solution 1

A simple way to make it a lot faster is to speed up your sum_of_two_abunds? method:

def sum_of_two_abunds?(num, array)
  array.each do |abun1|
    array.each do |abun2|
      current = abun1+abun2

      break if current > num
      return true if current == num
    end
  end

  return false
end

Instead of that inner loop, just ask the array whether it contains num - abun1:

def sum_of_two_abunds?(num, array)
  array.each do |abun1|
    return true if array.include?(num - abun1)
  end
  false
end

That's already faster than your Ruby code, since it's simpler and running faster C code. Also, now that that idea is clear, you can take advantage of the fact that the array is sorted and search num - abun1 with binary search:

def sum_of_two_abunds?(num, array)
  array.each do |abun1|
    return true if array.bsearch { |x| num - abun1 <=> x }
  end
  false
end

And making that Rubyish:

def sum_of_two_abunds?(num, array)
  array.any? do |abun1|
    array.bsearch { |x| num - abun1 <=> x }
  end
end

Now you can get rid of your own special case optimizations and fix your incorrect divsum (which for example claims that divsum(4) is 5 ... you should really compare against a naive implementation that doesn't try any square root optimizations).

And then it should finish in well under a minute (about 11 seconds on my PC).

Solution 2

Or you could instead ditch sum_of_two_abunds? entirely and just create all sums of two abundants and nullify their contribution to the sum:

def non_abundant_sum
  ceiling = 28123
  abundants = get_abundants(ceiling)
  numeri = (0..ceiling).to_a
  abundants.each { |a| abundants.each { |b| numeri[a + b] = 0 } }
  numeri.compact.sum
end

That runs on my PC in about 3 seconds.