From: Moses Hohman Date: 2005-12-06T06:30:08+09:00 Subject: Re: [QUIZ] Weird Numbers (#57) --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--