http://goo.gl/z1l7R

6830208.rb

require 'benchmark'
require "memoize"
include Memoize

UPPER_LIMIT = 1000000
MULTIPLIERS_COUNT = 6

def combinations_count(multipliers_count, upper_limit)
  return 1 if multipliers_count == 1

  combinations = [0]
  (-upper_limit.abs..upper_limit.abs).each do |first_multiplier|
    if (first_multiplier != 0 && upper_limit % first_multiplier == 0)
      combinations << combinations_count(multipliers_count-1, upper_limit / first_multiplier)
    end
  end
  combinations.inject(:+)
end

puts "Without memoization"
puts Benchmark.measure { puts combinations_count(MULTIPLIERS_COUNT, UPPER_LIMIT) }

memoize(:combinations_count)
puts "With memoization"
puts Benchmark.measure { puts combinations_count(MULTIPLIERS_COUNT, UPPER_LIMIT) }