Reply to thread

Message: [QUOTE="Ryan Leavengood, post: 4495092"] 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 =3D 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 =3D=3D 1 # A weird number is abundant but not semi-perfect. divisors =3D calc_divisors abundance =3D 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 =3D divisors.reject{|i| i > abundance}.reverse sum =3D to_search.sum if sum =3D=3D abundance false elsif sum < abundance true else not abundance.sum_in_subset?(to_search) end end else false end end def calc_divisors res=3D[1] 2.upto(Math.sqrt(self).floor) do |i| if self % i =3D=3D 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 =3D=3D 1 false else f =3D a.first remaining =3D a[1..-1] (self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining) end end end end if $0 =3D=3D __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 [/QUOTE]

Verification