--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

This is my first ruby quiz solution since Quiz #1 : ) Thanks, it was  
fun.

Moses


--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	name="test_weird.rb"
Content-Disposition: attachment;
	filename=test_weird.rb

require 'test/unit'
require 'weird'

class TestWeird < Test::Unit::TestCase
  def test_proper_divisors
    assert_equal [1], 11.proper_divisors
    assert_equal [1, 2, 3, 4, 6], 12.proper_divisors
    assert_equal [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45], 90.proper_divisors
  end
  
  def test_find_partition_from
    assert_equal nil, 2.send(:find_partition_from, [1])
    assert_equal [2], 2.send(:find_partition_from, [2])
    assert_equal [4,1], 5.send(:find_partition_from, [4, 3, 2, 1])
    assert_equal [175, 70, 50, 35, 14, 5, 1], 350.send(:find_partition_from, 350.proper_divisors.reverse)
  end
  
  def test_abundant
    assert_equal [12, 18, 20, 24], (1..25).find_all { |i| i.abundant? }
    assert 945.abundant?, "945 not abundant" # test an odd one for good measure, no real reason why
  end
  
  def test_semiperfect
    assert_equal [6, 12, 18, 20, 24], (1..25).find_all { |i| i.semiperfect? }
  end
  
  def test_weird
    assert 70.weird?, "70 not weird"
    assert !90.weird?, "90 weird"
  end
  
  def test_weird_numbers
    assert_equal [70, 836], weird_numbers_less_than(1000)
    assert_equal [], weird_numbers_less_than(70)
  end
end
--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	name="weird.rb"
Content-Disposition: attachment;
	filename=weird.rb

module Enumerable
  # syntactic sugar
  def sum
    inject(0) { |sum, element| sum += element }
  end
end

module Weird
  # Returns proper divisors of `self`, i.e. all divisors except `self`.
  # Optimization: cached to improve speed - only small benefit for `weird_numbers_less_than`.
  def proper_divisors
    @proper_divisors ||= calculate_proper_divisors.freeze
  end
  
  # True if `self` is abundant, i.e. < the sum of its proper divisors
  def abundant?
    self < proper_divisors.sum
  end
  
  # True if `self` is semiperfect, i.e. at least one subset of `self`'s divisors forms a partition of `self`
  def semiperfect?
    !find_partition_from(proper_divisors.reverse).nil?
  end
  
  # True if self is a weird number, i.e. abundant and not semiperfect.
  # Optimization: tests `abundant?` first because it's a lot faster.
  def weird?
    abundant? and not semiperfect?
  end
  
  # Syntactic sugar for Kernel's `weird_numbers_less_than` method below
  def even?
    self % 2 == 0
  end

  protected
  # Finds one partition of `self` composed of integers taken without replacement from
  # `set`. Only finds one, because all we need to know is whether there are any.
  #
  # Assumptions: set is sorted in decreasing order
  # Protected because I want to call it from a unit test via `send`.
  def find_partition_from(set)
    return nil if set.empty? # recursion termination condition: no partition found

    # find index of largest number < self in set (which is assume sorted in decreasing order)
    start = nil
    set.each_with_index do |element, index|
      return [element] if element == self # recursion termination condition: partition found 
      if element < self # found largest number < self
        start = index
        break
      end
    end

    # recursively construct partition
    partition = nil
    unless start.nil?
      start.upto(set.length-1) do |index|
        break unless partition.nil?
        biggest, tailset = set[index], set[(index+1)..-1]
        partition = (self - biggest).find_partition_from(tailset)
        partition.insert(0, biggest) unless partition.nil?
      end
    end

    partition
  end

  private
  # Actually calculates (i.e. not cached) and returns all proper divisors of `self`.
  # Optimization: it turned out that inserting the divisors in sorted order was slower,
  #               at least the way I tried it. Uniq does not pose much of a burden either.
  def calculate_proper_divisors
    return [] if self == 1
    result = [1]
    2.upto(Math.sqrt(self).floor) do |candidate|
      # add both candidate and quotient, since they are both divisors
      result << candidate << (self / candidate) if self % candidate == 0
    end
    result.sort.uniq # uniq is needed for perfect squares
  end
end

class Fixnum; include Weird; end
class Bignum; include Weird; end # optimistic about CPU power!

# Optimization: `check_odd` parameter: there are no odd weird numbers < 10**19 [Weisstein, 2005], so 
# in general you should leave this flag at its default value of `false`. This provides a modest speedup
# (something like a factor of 1.5. I think the reason it's not more is there are few odd abundant numbers).
#
# [Weisstein, 2005] Eric W. Weisstein. "Weird Number." From MathWorld--A Wolfram Web Resource.
#                   http://mathworld.wolfram.com/WeirdNumber.html
def weird_numbers_less_than(n, check_odd = false)
  (1...n).find_all { |number| (check_odd or number.even?) and number.weird? }
end

if __FILE__ == $0
  p weird_numbers_less_than(ARGV[0].to_i, (ARGV[1] == 'check_odd'))
end

--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed




On Dec 2, 2005, at 7:44 AM, Ruby Quiz wrote:

> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this  
> quiz until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 
> =-=-=-=-=-=-=
>
> by Martin DeMello
>
> A weird number is defined as a number, n, such that the sum of all  
> its divisors
> (excluding n itself) is greater than n, but no subset of its  
> divisors sums up to
> exactly n.
>
> Write a program to find all the weird numbers less than a given input.
>


--Apple-Mail-9-892176321--