From: "Brian Schröder" <ruby.brian@...>
Date: 2005-12-05T19:57:14+09:00
Subject: Re: [QUIZ] Weird Numbers (#57) Solution

Here is my solution, I don't think it is as fast as the others, but it
does never calculate a list of divisors. It scales quite badly

max   time
----------------
1000  0m0.714s
2000  0m2.756s
3000  0m6.351s
4000  0m13.404s
5000  0m16.806s
6000  0m27.031s
7000  0m33.482s
8000  0m44.111s
9000  0m54.781s
10000 1m6.179s

bschroed@black:~/svn/projekte/weird-numbers$ cat weird-numbers-be.rb
#!/usr/bin/ruby

# Break early version, checking if a number is weird
def weird_number(n)
  d  = r = s = nil
  sum = 0
  subset_sums = Hash.new
  subset_sums[0] = true
  for d in 1...n
    next unless n % d == 0
    # Calculate sum of all divisors
    sum += d
    # Calculate sums for all subsets
    subset_sums.keys.each do | s |
      return false if s + d == n
      subset_sums[s + d] = true
    end
  end
  sum > n
end

def weird_numbers(range)
  range.select { | n | weird_number(n) }
end

# Argument parsing
raise "Input exactly one number" unless ARGV.length == 1

max = ARGV[0].to_i

# Call it
puts weird_numbers(1..max)

cheers,

Brian