From: Ryan Leavengood <leavengood@...>
Date: 2005-12-05T02:11:04+09:00
Subject: Re: [QUIZ] Weird Numbers (#57) Solution

Here is my solution. It is pretty fast, but not quite as fast as
Rob's. For example his takes 6.797 seconds to calculate all weird
numbers up to 50000, whereas mine takes 7.375. Our solutions are quite
similar. Some of the other solutions are REALLY SLOW though. Probably
one of the biggest optimizations was using the square root of a given
number to calculate half the divisors, then use those to get the other
half. For example if 2 is a divisor of 14, then so is 14/2 = 7. For
big numbers this can be a massive speed-up.

Ryan

class Array
  def sum
    inject(0) do |result, i|
      result + i
    end
  end
end

class Integer
  def weird?
    # No odd numbers are weird within reasonable limits.
    return false if self % 2 == 1
    # A weird number is abundant but not semi-perfect.
    divisors = calc_divisors
    abundance = divisors.sum - 2 * self
    # First make sure the number is abundant.
    if abundance > 0
      # Now see if the number is semi-perfect. If it is, it isn't weird.
      # First thing see if the abundance is in the divisors.
      if divisors.include?(abundance)
        false
      else
        # Now see if any combination sums of divisors yields the abundance.
        # We reject any divisors greater than the abundance and reverse the
        # result to try and get sums close to the abundance sooner.
        to_search = divisors.reject{|i| i > abundance}.reverse
        sum = to_search.sum
        if sum == abundance
          false
        elsif sum < abundance
          true
        else
          not abundance.sum_in_subset?(to_search)
        end
      end
    else
      false
    end
  end

  def calc_divisors
    res=[1]
    2.upto(Math.sqrt(self).floor) do |i|
      if self % i == 0
        res << i
      end
    end
    res.reverse.each do |i|
      res << self / i
    end
    res
  end

  def sum_in_subset?(a)
    if self < 0
      false
    elsif a.include?(self)
      true
    else
      if a.length == 1
        false
      else
        f = a.first
        remaining = a[1..-1]
        (self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining)
      end
    end
  end
end

if $0 == __FILE__
  if ARGV.length < 1
    puts "Usage: #$0 <upper limit>"
    exit(1)
  end

  puts "Weird numbers up to and including #{ARGV[0]}:"
  70.upto(ARGV[0].to_i) do |i|
    puts i if i.weird?
  end
end