Here is my solution. Its not the most beautiful thing in the world, but its effective. ----------------------------------------- def weirdo_exhaustive(from, max) puts "none found" and return 0 if max < 70 (from..max).each do |num| if num % 2 == 0 list, sum= [], 0 (1...num).each do |div| list << div and sum += div if num % div == 0 end puts "==" + num.to_s if sum > num and has_sum(num, list) == false end end end def has_sum(num, array) if array.is_a? Integer then return false end sum = 0 array.each do |val| sum += val end if sum === num then return true end #this next line saves a BUNCH of checks. if sum < num then return false end array.each do |removeme| copy = array.dup copy.delete(removeme) if copy.size > 1 and has_sum(num, copy) == true then return true end end return false end ---------------------------------------- It took a good number of optimizations that make it less pretty, but much faster. The first time I ran it it took 4 hours to reach 1,000. Its faster than that now, but its still somewhere around O(3^n). SO... I thought of a way to speed up the algorithm a lot! So, with a *few* more optimizations, here's the weirdo_fast algorithm. ------------------------------------------------------- def weirdo_fast(max) list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, # 83312,91388,113072,243892,254012,338572,343876,388076, # 519712,539744,555616,682592,786208,1188256,1229152,1713592, # 1901728,2081824,2189024,3963968 ] list.each do |num| puts num if num <= max end if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1], max) end end ----------------------------------------------------- A little faster, eh? It will start exhaustively searching if your max is out of its range.... but I warn you, my computer has been calculating 3963970 for the last 24 hours. And, not the range up to it, just that number. Remember, its 3^3963970 = 62_286_091_158_062_773_000 which takes a minute to calculate. Well, with my other optimizations, its a tad faster than that.... a tad. I'm interested to see if anyone else found a much better way to test for has_sum(num, array). It seems to me like there must be a clever mathematical trick for getting the job done. Or perhaps the only clever way is my "fast" algorithm. But, that's not even that clever. -Hampton Catlin. removed_email_address@domain.invalid

on 2005-12-04 15:28

on 2005-12-04 16:29

On 12/4/05, Hampton <removed_email_address@domain.invalid> wrote: > Here is my solution. Its not the most beautiful thing in the world, but > its effective. [snip] I could not find any fast solution.. -- Simon S. # Weird Numbers # Simon S. <removed_email_address@domain.invalid> def divisors(value) ary = [] (value/2).times do |i| div = i + 1 ary << div if value % div == 0 end ary end $bits = [] 32.times do |bit| $bits << 2 ** bit end def has_subset_equal_to(divs, value) pairs = divs.zip($bits) 1.upto(2 ** divs.size - 1) do |i| sum = 0 pairs.each{|div,b| sum+=div if (i&b)>0 } return true if sum == value end false end def find_weird_numbers(range_min, range_max) ary = [] range_min.upto(range_max) do |value| divs = divisors(value) sum = divs.inject(0){|a,b|a+b} ary << [value, divs] if sum > value end res = [] ary.each do |value, divs| if !has_subset_equal_to(divs, value) puts "##{value} is a WEIRD NUMBER" res << value else puts "##{value} is nothing" end end p res end p find_weird_numbers(1, 100)

on 2005-12-04 17:47

On Dec 4, 2005, at 7:27 AM, Hampton wrote: > list.each do |num| > puts num if num <= max > end > if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1], > max) end > end > > ----------------------------------------------------- > > A little faster, eh? Bingo. I was actually thinking of screen scraping them from on of the encyclopedias mentioned in the quiz thread, but I like this even better. Nice job. James Edward G. II

on 2005-12-04 18:03

James, I was starting to do that... I was building my HTTP object, and I noticed how hard it was going to be to parse...... so I said screw it, I'll make it easier. And FASTER! It would even run with 6k of ram! -h.

on 2005-12-04 18:32

On 12/4/05, Simon S. <removed_email_address@domain.invalid> wrote: Here is my solution. <http://tinyurl.com/9qjfg> (needs data-url support in your browser) I basically used the definition of a "weird number" to implement the solution. This makes the code pretty, but also really, really slow. --- #!/usr/bin/ruby # Rubyquiz #57 -- Weird Numbers # ----------------------------- # Levin A. <removed_email_address@domain.invalid> module Enumerable def sum inject(0) {|s,elem| s+elem} end end class Array def subsets (0...2**length).collect {|i| values_at(*(0...length).find_all {|j| i&(1<<j)>0 }) } end end class Integer def abundant? divisors.sum > self end def semiperfect? divisors.subsets.any? { |set| set.sum == self } end def weird? abundant? and not semiperfect? end def divisors (1...self).select { |i| self % i == 0 } end end if __FILE__ == $0 0.upto(ARGV[0].to_i) { |i| if i.weird? puts i else warn "#{i} is not weird" if $DEBUG end } end

on 2005-12-04 18:56

#!ruby =begin The Quiz was real fun and I spent quite a lot of time on it. Below source is rather easy, but believe me I tried lots of different ways (such as dynamic binary knapsacks etc.), most of them suck because they need to many method calls. The code takes about 30 seconds to find all Weird Numbers up to 10_000: 70, 836, 4030, 5830, 7192, 7912, 9272. The code doesn't scale rather well, the caches would need to be optimized for that. =end class Integer # 70, 836, 4030, 5830, 7192, 7912, 9272, 10430 def weird? !has_semiperfect? && !weird2? end SEMIPERFECT = {nil => 'shortcut'} def weird2?(divisors=proper_divisors) return true if divisors.any? { |x| SEMIPERFECT[x] } if brute(self, divisors) SEMIPERFECT[self] = true else false end end SMALL_SEMIPERFECT = [6, 20, 28] # + [88, 104, 272] def has_semiperfect? SMALL_SEMIPERFECT.any? { |v| self % v == 0 } end def proper_divisors d = [] sum = 0 2.upto(Math.sqrt(self)) { |i| if self % i == 0 d << i << (self / i) sum += i + (self / i) end } return [nil] unless sum > self d << 1 end def brute(max, values) values.sort! values.delete max / 2 max = max / 2 s = values.size (2**s).downto(0) { |n| sum = 0 s.times { |i| sum += values[i] * n[i] } return true if sum == max } false end end if ARGV[0] n = Integer(ARGV[0]) else n = 10_000 end 2.step(n, 2) { |i| p i if i.weird? } __END__

on 2005-12-04 19:13

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

on 2005-12-04 19:29

Mine's *really* fast up to 3,963,968.... then it slows down just a *tad*. ;) For instance, mine can do up to 50,000 in 0.0012 seconds on a 300mhz processor. And it can do 3 million in 0.014338 seconds. Actually, I think I can speed up my exhausted.... {walks away to code}

on 2005-12-04 19:34

On 12/4/05, Hampton <removed_email_address@domain.invalid> wrote: > Mine's *really* fast up to 3,963,968.... then it slows down just a > *tad*. ;) > > For instance, mine can do up to 50,000 in 0.0012 seconds on a 300mhz > processor. > And it can do 3 million in 0.014338 seconds. Except your solution is missing tons and tons of valid weird numbers. Ryan

on 2005-12-04 19:38

Here's my solution. It looks pretty close to others. Not too fast, but it gets the job done. I think after I get a chance to look at other solutions I can write a some of this better. class Integer def divisors divs = [] 1.upto(Math.sqrt(self).to_i) do |i| divs += [i ,self/i].uniq if (self%i == 0) end divs.sort.reverse #reverse speeds things up a bit end def weird? divs = self.divisors - [self] return false if divs.sum < self divs.each_combination do |comb| return false if comb.sum == self end return true end end class Array def each_combination (2**self.length).times do |comb| curr = [] self.length.times do |index| curr << self[index] if(comb[index] == 1) end yield curr end end def sum inject(0) { |sum, i| sum + i } end end max = (ARGV[0] || 10000).to_i max.times do |i| puts i if i.weird? end -----HornDude77

on 2005-12-04 19:46

On 12/4/05, Ryan L. <removed_email_address@domain.invalid> wrote: [snip] > remaining = a[1..-1] > (self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining) > end > end > end > end nice and speedy.. mine is awful and slow.

on 2005-12-04 20:10

On 12/4/05, James Edward G. II <removed_email_address@domain.invalid> wrote: > > 519712,539744,555616,682592,786208,1188256,1229152,1713592, # > > A little faster, eh? > > Bingo. > > I was actually thinking of screen scraping them from on of the > encyclopedias mentioned in the quiz thread, but I like this even better. > > Nice job. I don't know, I think this is cheating. Plus he is missing a bunch of weird numbers in his list. Ryan

on 2005-12-04 20:22

Here is my solution (it's optimized for statistics not for speed). I don't use things like someone tried all odd numbers up to 10**18 because doesn't change the algorithm.. I'll use that in my speed optimized version.. ############# =begin References: http://en.wikipedia.org/wiki/Divisor_function http://en.wikipedia.org/wiki/Weird_number Eric W. Weisstein. "Weird Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/WeirdNumber.html Eric W. Weisstein. "Semiperfect Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/SemiperfectNumber.html Eric W. Weisstein. "Perfect Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PerfectNumber.html Eric W. Weisstein. "Divisor Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DivisorFunction.html Eric W. Weisstein. "Mersenne Prime." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/MersennePrime.html Eric W. Weisstein. "Abundance." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Abundance.html =end class Integer $prime_factors = Hash.new # we cache prime factors... def prime_factors position = -1 if cached = $prime_factors[self] # cached? return cached # yes end if self == 1 # we have 1 we are done return $prime_factors[self]=[] # return no factors elsif position<0 # we havn't reached factor 5 yet if self&1 == 0 # test factor 2 return $prime_factors[self]=[2,*(self>>1).prime_factors] elsif self%3 == 0 # and factor 3 return $prime_factors[self]=[3,*(self/3).prime_factors] end end loop do position+=6 # increment position by 6 if position*position > self # we have a prime number return it return $prime_factors[self]=[self] elsif (quo,rem = divmod(position)) and rem.zero? # test 6n-1 return $prime_factors[self]=[position,*quo.prime_factors (position-6)] elsif (quo,rem = divmod(position+2)) and rem.zero? # and 6n+1 return $prime_factors[self]=[position+2,*quo.prime_factors (position-6)] end end end def distinct_prime_factors # rle encode the prime factors ;) distinct_prime_fac = Hash.new{0} # setup the hash prime_factors.each do |prime_factor| # fill it distinct_prime_fac[prime_factor]+=1 end distinct_prime_fac.to_a.sort_by{|(fac,count)|fac} # and return it as sorted array end def divisors # get the divisors (not needed for divisor sum) divs = [] # store divisors here n = 1 # start with 1 loop do break if n*n > self # done if (qua,rem = divmod(n)) and rem.zero? # test for division divs << qua # add divisors divs << n end n+=1 end divs.uniq.sort[0..-2] # we don't want self end def semi_perfect? deficient=false # final test cached_abundance = abundance return deficient if cached_abundance < 0 # deficient return the argument return true if cached_abundance == 0 # perfect => semi perfect too possible_values = {0=>true} # store all possible values in a hash divs = self.divisors # get the divisors div_sum_left = divs.inject(0){|a,b|a+b} # get the divisor sum pos_2 = div_sum_left - self # this is a possibility too divs.reverse.each do |div| # for each divisor possible_values.keys.each do |value| # and each possible value if value+div_sum_left < self # check wether it can reach the number with the divisors left possible_values.delete(value) # if not delete the number (huge speedup) end new_value = value+div # we create a new possible value including the divisor if new_value == self or new_value == pos_2 # if it is the number it's semi perfect return true elsif new_value < self # if it's less than the number it could be semi perfect possible_values[new_value]=true # add it to the possiblities end # if it's more than the value we can ignore it end div_sum_left-=div # the current divisor isn't left anymore end false # we found no way to compose the number using the divisors end def restricted_divisor_sum # uses the formular from wikipedia distinct_prime_factors.map do |(fac,count)| comm_sum = 1 comm_mul = 1 count.times do comm_sum += (comm_mul*=fac) end comm_sum end.inject(1){|a,b|a*b}-self end def perfect? # perfect numbers have the form 2**(n-1)*(2**n-1) where n is prime (and small ;) ) return false if self&1 == 1 # it isn't known weather there are odd perfect numbers.. but it's irrelevant for my algorithm doubled = self * 2 # the perfect number is a triangular number of the form (n*(n+1))/2 doubled_root = Math.sqrt(doubled).floor # if we double it and take the floored square root we get n return false unless doubled == doubled_root*(doubled_root+1) # if we don't get n it isn't perfect doubled_root_string = (doubled_root+1).to_s(2) # from the first line we know n+1 has to be of the form 2**n return false unless doubled_root_string.count('1')==1 # we check that here return false unless (doubled_root_string.size-1).prime_factors.size == 1 # and n ha to be a prime return false unless self.abundance == 0 # if it passes all the earlier test we check it using the abundance true # and if it passes it's perfect end def abundance self.restricted_divisor_sum-self end end require 'benchmark' max_num = Integer(ARGV.shift||'1000') rescue 1000 # read a number from the command line new_semi_perfects = [] # store semi perfect numbers that can't be constructed using other semi perfect numbers STDOUT.sync = true puts "Weird Numbers Up To #{max_num}:" #begin_stat perfect_count = 0 composed_semi_perfect_count = 0 new_semi_perfect_count = 0 weird_count = 0 deficient_count = 0 record_nums = (1..80).map{|n|max_num*n/80} record_nums_left = record_nums.dup next_record = record_nums_left.shift recorded_times = [] init_time = [Benchmark.times,Time.now] min_odd = 10**17 #end_stat (1..max_num).each do |test_num| # counting loop if test_num == next_record #stat recorded_times << [Benchmark.times,Time.now] #stat next_record = record_nums_left.shift #stat end #stat if test_num.perfect? # it's perfect new_semi_perfects << test_num perfect_count += 1 #stat next end do_next = false new_semi_perfects.each do |semi_per| if test_num % semi_per == 0 # is it possible to compose the current number using a semi-perfect number? do_next = true # yes composed_semi_perfect_count += 1 #stat break end end next if do_next # no case test_num.semi_perfect? nil # we don't care about deficient numbers when true # but we care about semi perfects new_semi_perfects << test_num new_semi_perfect_count += 1 #stat when false # and even more about abundand non semi perfects puts test_num weird_count += 1 #stat else #stat deficient_count += 1 #stat end end #end #begin_stat final_time = [Benchmark.times,Time.now] digit_length = max_num.to_s.size def form_float(num) "%12s" % ("%im%#{7}ss" % [(num/60).floor,("%.4f" % (num %60))]).tr (" ","0") end def rel(x,y) "%#{y.to_s.size}i (%6s%%)" % [x,"%3.2f" % (x/y.to_f*100)] end puts "Stats" puts "Time:" puts "- User: "+form_float(ut = final_time.first.utime - init_time.first.utime) puts "- System: "+form_float(st = final_time.first.stime - init_time.first.stime) puts "- U+S: "+form_float(ut+st) puts "- Real: "+form_float(final_time.last - init_time.last) puts puts "Numbers:" puts "- Total "+rel(max_num,max_num) puts "- Weird "+rel(weird_count,max_num) puts "- Perfect "+rel(perfect_count,max_num) puts "- Deficient "+rel(deficient_count,max_num) puts "- Abundand "+rel(abundand_count = max_num-perfect_count- deficient_count,max_num) puts "- Semi-Perfect "+rel(abundand_count-weird_count,max_num) puts " (w/o perfects)" puts "" puts "- Passed 1st "+rel(max_num-perfect_count,max_num) puts " (perfect test)" puts "- Passed 2nd "+rel(new_semi_perfect_count+weird_count +deficient_count,max_num) puts " (composed test)" puts "- Passed 3rd "+rel(new_semi_perfect_count+weird_count,max_num) puts " (deficient test)" puts "- Uncomposed "+rel(new_semi_perfects.size,max_num) puts " (semi-perfects that arn't a multiply of another semi-perfect)" puts if recorded_times.size >= 80 puts "Graphs:" puts process_plot = [] real_plot = [] first_ustime = init_time.first.utime+init_time.first.stime first_realtime = init_time.last recorded_times.each do |(process_time,realtime)| process_plot << process_time.utime+process_time.stime - first_ustime real_plot << realtime - first_realtime end max_process = process_plot.last step_process = max_process / 22 max_real = real_plot.last step_real = max_real / 22 def plot(plot_data,max,step) 22.downto(0) do |k| res = "" res = form_float(max) if k == 22 while res.size != plot_data.size val = plot_data[res.size] lower_range = k*step res << ( val >= lower_range ? (val < lower_range+step ? '#' : ':') : ' ' ) end puts res end end puts "Y: Realtime X: Number" plot(real_plot,max_real,step_real) puts "%-40s%40s"% [1,max_num] puts "Y: System+Usertime X: Number" plot(process_plot,max_process,step_process) puts "%-40s%40s"% [1,max_num] puts end #end_stat __END__

on 2005-12-04 21:19

I've got an optimization I haven't seen anyone else use yet. My solution is roughly 20% faster than Ryan's. The trick is that any number of the form k*(2^m)*p where m > 1 and p is a prime such that 2 < p < 2^(m+1) is semiperfect (according to wikipedia). This rules out many numbers, and its cheaper than a thorough search of subsets. #!/usr/bin/ruby def weird(max) primes = sieve(max*2) 70.step(max,2){|n| puts n if weird?(n,primes) } end def weird?(n,primes) divs = divisors(n) abund = divs.inject(0){|a,b| a+b} - n return false if abund <= 0 return false if spfilter(n,primes) return false if divs.include? abund smalldivs = divs.reverse.select{|i| i < abund} not sum_in_subset?(smalldivs,abund) end def sum_in_subset?(lst,n) #p [lst,n] return false if n < 0 return true if lst.include? n return false if lst.size == 1 first = lst.first rest = lst[1..-1] sum_in_subset?(rest, n-first) or sum_in_subset?(rest,n) end def divisors(n) result = [] sr = Math.sqrt(n).to_i (2 .. sr).each {|d| if n.modulo(d) == 0 result << d end } return [1] if result.empty? hidivs = result.map {|d| n / d }.reverse if hidivs[0] == result[-1] [1] + result + hidivs[1..-1] else [1] + result + hidivs end end def spfilter(n,primes) m = 0 save_n = n while n[0]==0 m += 1 n >>= 1 end return false if m == 0 low = 2 high = 1 << (m+1) primes.each {|p| return false if p > high if p > low return true if n%p == 0 end } raise "not enough primes while checking #{save_n}" end # Sieve of Eratosthenes def sieve(max_prime) candidates = Array.new(max_prime,true) candidates[0] = candidates[1] = false 2.upto(Math.sqrt(max_prime)) {|i| if candidates[i] (i+i).step(max_prime,i) {|j| candidates[j] = nil} end } result = [] candidates.each_with_index {|prime, i| result << i if prime } result end weird(ARGV[0].to_i) regards, Ed

on 2005-12-04 21:40

On Dec 4, 2005, at 11:29 AM, Ryan L. wrote: > I don't know, I think this is cheating. It's cheating to get correct answers quickly? ;) > Plus he is missing a bunch of weird numbers in his list. I haven't compared the Array in question with the posted sequences. Perhaps it's not very complete. Let me ask you this though, since we're talking about this: Which is easier to debug, the sequence list or a broken calculation solution? Didn't the solution also brute force answers when it left its list of known numbers? One last question: How well does your presumably fast solution do when it goes beyond the listed sequence? Does it still find lots of answers, quickly? I'm really not trying to be mean here and I apologize if I'm coming off that way. I think what Hampton hit on is a simple cache optimization. It's fast and very effective. I don't think we should be so quick to toss it out as a viable approach... James Edward G. II

on 2005-12-04 22:01

#!/usr/bin/env ruby # # Ruby Q. Weird Numbers solution. # # I found only two significant optimizations: # 1. Use continuations when generating the powerset of # divisors to sum. Evaluate each sum immediately # and break upon determining the number is semiperfect. # 2. Sort the divisors in descending order so that # subsets involving the larger divisors are considered # first. # # On my machine, generating results for numbers up to 5000 # took less than a minute. Generating results up to 12000 # took almost twenty minutes. # # This powerset implementation was inspired by a post to # Ruby-Talk by Robert K. on May 14, 2004: # http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/... # # module Enumerable def powerset for element_map in 0...(1 << self.length) do subset = [] each_with_index do |element, index| subset << element if element_map[index] == 1 end yield subset end end end class Array def sum return self.inject { |total,x| total += x } end end class Integer def weird? divs = self.divisors.reverse return false unless divs.sum > self divs.powerset { |subset| return false if subset.sum == self } return true end def divisors list = [] (1..Math.sqrt(self).to_i).each do |x| if (self / x) * x == self list << x list << (self / x) unless x == 1 or (self / x) == x end end return list.sort end end #################### (1..5000).each { |n| puts n if n.weird? }

on 2005-12-04 22:41

On 12/4/05, James Edward G. II <removed_email_address@domain.invalid> wrote: > > It's cheating to get correct answers quickly? ;) Well something had to generate those answers in the first place, and for that I'd take my, Rob, or Edward's solution any day. > I haven't compared the Array in question with the posted sequences. > Perhaps it's not very complete. Let me ask you this though, since > we're talking about this: Which is easier to debug, the sequence > list or a broken calculation solution? Well I certainly debugged mine by looking at the pre-existing list, which was useful. But the fact that his list was missing things really caused me pause, because if someone depended on that list to be accurate, they would be in trouble. > Didn't the solution also brute force answers when it left its list of > known numbers? Yes but his brute-force algorithm is extremely slow, and his list is wrong. > One last question: How well does your presumably fast solution do > when it goes beyond the listed sequence? Does it still find lots of > answers, quickly? Of the three fastest solutions so far (Edward's, Rob's and mine), all continue to generate answers at a similar rate, consistently. For example, to generate up to 100000, the time was 16.687, 17.281 and 18.469 seconds (in the order listed above, i.e. mine is slowest.) Since there are 204 weird numbers between 0 and 100000, each algorithm generates about 11-12 per second. > I'm really not trying to be mean here and I apologize if I'm coming > off that way. Well I've probably come off as mean to Hampton, and I don't really want to come off that way either. But it does rub me the wrong way to have someone call their solution fast when the solution is WRONG. > I think what Hampton hit on is a simple cache optimization. It's > fast and very effective. I don't think we should be so quick to toss > it out as a viable approach... His caching optimization is certainly a good idea (and fairly obvious), though it would be better if it actually generated the cache and reused it so that subsequent runs got faster. I may code up something like this. Ryan

on 2005-12-04 22:45

Which ones are missing? My set is.... [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, # 83312,91388,113072,243892,254012,338572,343876,388076, # 519712,539744,555616,682592,786208,1188256,1229152,1713592, # 1901728,2081824,2189024,3963968 ]

on 2005-12-04 22:53

I did mine with a good dose of humor. I certainly know that my weirdo_exhaustive is slow... hell, I called it both "weirdo" and "exhaustive". However, I thought of the fast solution as a bit of humor for everyone to enjoy. I do think it has merit in *some* ways only because its damn hard to make anything go faster than that. I did not mean any previous comments to be "i'm better than you" in any real way. They were all made tounge in cheek because of course just accessing an array is going to be orders of magnatude faster. These quizes are not for points and there is no "winner" (at least not that i've seen assigned in previous iterations of the quiz. In fact, there is never any qualifications for what makes the best one! And yes, I did use the wrong number set. I found the number set for primitive weird numbers, not exhaustive. I used this: http://www.research.att.com/cgi-bin/access.cgi/as/... As opposed to this: http://www.research.att.com/cgi-bin/access.cgi/as/... My mistake.... But, lets all be friends! How about a beer? -hampton c.

on 2005-12-04 22:57

On Dec 4, 2005, at 2:40 PM, Ryan L. wrote: > On 12/4/05, James Edward G. II <removed_email_address@domain.invalid> wrote: >> >> It's cheating to get correct answers quickly? ;) > > Well something had to generate those answers in the first place, and > for that I'd take my, Rob, or Edward's solution any day. [snip] > His caching optimization is certainly a good idea (and fairly > obvious), though it would be better if it actually generated the cache > and reused it so that subsequent runs got faster. I may code up > something like this. NOW you're talking! You could just calculate them once and that's the best of both worlds... ;) James Edward G. II

on 2005-12-04 23:01

Ryan- It was supposed to be a funny statement. I even used a ;) And of course calling my "exhaustive" (hint in the name) a *tad* slower is absolutely, 100% absurdist. I used the wrong AO list as mentioned in my other response. I apologize to all those who my not paying attention to "primitive weird numbers" and "weird numbers" hurt in the process. This quiz is for *fun* not competition. -hampton. PS: For further clarification, about 50% of this message is also supposed to be somewhat amusing.

on 2005-12-04 23:01

On Dec 4, 2005, at 2:52 PM, Hampton wrote: > However, I thought of the fast solution > as a bit of humor for everyone to enjoy. I do think it has merit in > *some* ways only because its damn hard to make anything go faster than > that. It is a valid technique. It can probably be used to make the fastest posted solutions even faster. You're example maybe wasn't the ideal representation, but I think Ryan hit on a great one in his last message. That's all I was saying. Don't overlook what can help! ;) > But, lets all be friends! How about a beer? <laughs> Seriously, I didn't mean to upset a single soul. My truest apologies if I did. James Edward G. II

on 2005-12-04 23:01

Just up to 100,000 you are missing 191 weird numbers. Run my, Rob or Edward's solution to see exactly which ones. Up to 3963968, I don't even want to guess how many are missing. Even Edward's solution would take some time to find out. They aren't quite as rare as you think. Ryan

on 2005-12-04 23:10

I realized it was a list of primitive weird numbers instead of weird numbers. Down below I have links to the two lists of numbers. My bad. -hampton.

on 2005-12-04 23:14

On 12/4/05, Hampton <removed_email_address@domain.invalid> wrote: > I did mine with a good dose of humor. Hehehe, I could see that a bit. > I certainly know that my weirdo_exhaustive is slow... hell, I called it > both "weirdo" and "exhaustive". However, I thought of the fast solution > as a bit of humor for everyone to enjoy. I do think it has merit in > *some* ways only because its damn hard to make anything go faster than > that. Well there is no doubt that in a real application there would be a cache for weird numbers, should that application need them frequently. > I did not mean any previous comments to be "i'm better than you" in any > real way. They were all made tounge in cheek because of course just > accessing an array is going to be orders of magnatude faster. Fair enough, and I would have appreciated the solution more had it been correct. > These quizes are not for points and there is no "winner" (at least not > that i've seen assigned in previous iterations of the quiz. In fact, > there is never any qualifications for what makes the best one! Of course, but quizzes like this benefit from analyzing which algorithms are the fastest. This one in particular had a HUGE margin between the fast and slow solutions. Other quizzes are more about the structure of the code and solving the problem elegantly, and you won't see me or anyone else getting out the benchmarking tools. > And yes, I did use the wrong number set. I found the number set for > primitive weird numbers, not exhaustive. > > I used this: > http://www.research.att.com/cgi-bin/access.cgi/as/... > As opposed to this: > http://www.research.att.com/cgi-bin/access.cgi/as/... > > My mistake.... I see, easy enough mistake to make I suppose. > But, lets all be friends! How about a beer? Don't take my criticism as being hostile. In fact if you read this list you'll find me most helpful when newbies have problems. But I don't hesitate to tell people when they are wrong. A beer would be fine if you happen to live where I am, in South Florida ;) Ryan

on 2005-12-04 23:30

I'm from Jacksonville originally, but now live in the cold tundra of Toronto. However, I will be there for christmas! Yes, it was hostile. And I will beat up both your *and* your mom for what you said about my misfunctioning algorithm! ;) -hampton. PS: However, I will say that on the next one, I'm going to be debugging just a tad more.

on 2005-12-04 23:51

On 12/4/05, James Edward G. II <removed_email_address@domain.invalid> wrote: > > NOW you're talking! You could just calculate them once and that's > the best of both worlds... ;) Well I coded this up. Instead of pasting my whole solution I'll just paste the cache class and the updated "main" block for my solution. I've also added some timing code so one can see the speed improvements. To try this out, replace my if $0 == __FILE__ code from my original solution with all of the following: class WeirdCache def initialize(filename='.weirdcache') @filename = filename if test(?e, filename) @numbers = IO.readlines(filename).map do |i| i.chomp.to_i end else @numbers=[] end @added = false end def each(&block) @numbers.each(&block) end def <<(i) @added = true @numbers << i end def save if @added File.open(@filename, File::RDWR|File::CREAT|File::TRUNC) do |file| file.puts @numbers 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]}:" start = Time.now cache = WeirdCache.new at_exit {cache.save} limit = ARGV[0].to_i i = 69 cache.each do |i| if i <= limit puts i end end (i+1).upto(limit) do |j| if j.weird? cache << j puts j end end puts "This took #{Time.now - start} seconds" end

on 2005-12-04 23:59

> His caching optimization is certainly a good idea (and fairly > obvious), though it would be better if it actually generated the cache > and reused it so that subsequent runs got faster. I may code up > something like this. Why not take the Seti-At-Home approach and parcel out ranges of numbers that can be checkout by home users with spare cycles on their machines, searched for WeirdNumbers and reported back to the mothership.

on 2005-12-05 00:28

On Dec 4, 2005, at 3:47 PM, Ryan L. wrote: > On 12/4/05, James Edward G. II <removed_email_address@domain.invalid> wrote: >> >> NOW you're talking! You could just calculate them once and that's >> the best of both worlds... ;) > > Well I coded this up. Just so others see the effect of this, here are some timings from runs. The first is Ryan's original code, the second is the new version's first (cache-less) run, and the third is the code taking advantage of the cache: Neo:~/Documents/Ruby/Ruby Q.$ time ruby solutions/Ryan\ Leavengood/ weird_numbers.rb 50000 Weird numbers up to and including 50000: ... real 0m6.258s user 0m6.170s sys 0m0.046s Neo:~/Documents/Ruby/Ruby Q.$ time ruby solutions/Ryan\ Leavengood/ weird_numbers.rb 50000 Weird numbers up to and including 50000: ... This took 6.231214 seconds real 0m6.253s user 0m6.169s sys 0m0.044s Neo:~/Documents/Ruby/Ruby Q.$ time ruby solutions/Ryan\ Leavengood/ weird_numbers.rb 50000 Weird numbers up to and including 50000: ... This took 0.096576 seconds real 0m0.116s user 0m0.102s sys 0m0.011s James Edward G. II

on 2005-12-05 00:50

This was really a good and enjoyable exercise. I learnt a lot. One of the best solutions is made by Leavengood. I would like to point out a small error. 36.calc_divisors returns [1,2,3,4,6,6,9,12,18,36]. 6 is reckoned twice. This seems to have no implication on the result though. 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 The part I appreciate most is the beautiful and fast handling of the binary set: 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 I also learnt that Ruby is really quick once you leave the debugger! Here is my solution. It is short but slow. def divisors(n) (1..n.div(2)).collect {|i| i if n.modulo(i)==0}.compact end def sum(arr) arr.inject(0) {|sum,element| sum+element} end def subset?(n, divisors) arr=[] divisors.each do |i| arr.concat arr.collect {|j| i+j} arr << i arr.uniq! return true if arr.member?(n) end false end def weird(n) return if n.modulo(2)==1 coll = divisors(n) diff = sum(coll)-n return if diff <= 0 return n unless subset?(diff,coll) end def all_weird(n) (1..n).collect {|i| weird(i)}.compact end assert_equal [1,2,3,4,6], divisors(12) assert_equal [1,2,5,7,10,14,35], divisors(70) assert_equal 16, sum(divisors(12)) assert_equal 74, sum(divisors(70)) assert_equal true, subset?(12,divisors(12)) assert_equal false, subset?(70,divisors(70)) assert_equal false, subset?(4,divisors(70)) assert_equal nil, weird(2) assert_equal nil, weird(12) assert_equal nil, weird(20) assert_equal 70, weird(70) assert_equal [70], all_weird(70) assert_equal [70,836], all_weird(836) Christer

on 2005-12-05 01:25

On 12/4/05, Christer N. <removed_email_address@domain.invalid> wrote: > This was really a good and enjoyable exercise. I learnt a lot. One of > the best solutions is made by Leavengood. I would like to point out a > small error. 36.calc_divisors returns [1,2,3,4,6,6,9,12,18,36]. 6 is > reckoned twice. This seems to have no implication on the result though. Thank you for the compliment and for catching the error. It seems calc_divisors will always have two divisors for the square root of any perfect square. I suppose it was just luck that this didn't mess up the algorithm. But there might be some number where this could cause a problem, so res.uniq should probably be called at the end. Ryan

on 2005-12-05 02:21

Christian N. <removed_email_address@domain.invalid> wrote: > #!ruby > =begin > > The Quiz was real fun and I spent quite a lot of time on it. Below > source is rather easy, but believe me I tried lots of different ways > (such as dynamic binary knapsacks etc.), most of them suck because they > need to many method calls. Same here - I tried a bunch of stuff, but the code ended up being rather slow, so I discarded it. It's still rather slow :( N = ARGV[0].to_i # precalculate the list of primes def primes_to(n) sieve = (0..n).to_a 2.upto(n) {|i| next unless sieve[i] (i*i).step(n, i) {|j| sieve[j] = nil} } sieve[2..-1].compact end PRIMES = primes_to(N) # helper method class Array def bsearch(n) i = 0 j = size - 1 k = (i+j)/2 while i < k if at(k) > n j = k elsif at(k) < n i = k else return k end k = (i+j)/2 end return i end end # factorisation routines - find the prime factors, then combine them to get a # list of all factors def prime_factors(x) pf = Hash.new {|h, k| h[k] = 0} PRIMES.each {|p| break if p > x while x % p == 0 pf[p] += 1 x /= p end } pf end def expand_factors(f, pf) return f if pf.empty? p, n = pf.shift powers = [p] (n-1).times { powers << p * powers[-1] } g = f.dup powers.each {|i| f.each {|j| g << i*j } } expand_factors(g, pf) end def factors(n) a = expand_factors([1], prime_factors(n)).sort a.pop a end # and finally, the weirdness test def weird?(n) fact = factors(n) # # test for abundance (sum(factors(n)) > n) sum = fact.inject {|a, i| a+i} return false if sum < n # weird numbers are abundant # now the hard part partials = [0] fact.each {|f| if sum < n # discard those partials that are lower than the sum of all remaining # factors i = partials.bsearch(n-sum) return false if partials[i] == (n-sum) partials = partials[(i+1)..-1] end sum -= f # sum of all remaining factors temp = [] partials.each {|p| j = f + p break if j > n l = n - j next if l > sum return false if (j == n) or (l == sum) temp << j } # handwriting a merge sort didn't help :-/ partials = partials.concat(temp).sort.uniq } return true end def all_weird(n) weird = [] # odd numbers are not weird (unproven but true for all n < 10^17) 2.step(n, 2) {|i| weird << i if weird?(i) } weird end require 'benchmark' Benchmark.bm(10) {|x| [1000,10000,20000].each {|n| x.report("#{n}") {p all_weird(n)} } } martin

on 2005-12-05 02:30

On 12/4/05, Christer N. <removed_email_address@domain.invalid> wrote: > false > else > f = a.first > remaining = a[1..-1] > (self - f).sum_in_subset?(remaining) or > sum_in_subset?(remaining) > end > end > end Yes, this is quite nice. I rewrote it a bit so that it does not need the nested ifs. What do you think? def sum_in_subset?(div = self.divisors) return false if self < 0 return false if div.empty? return true if div.include?(self) f, remaining = div[0], div[1..-1] (self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining) end Viele GrÃ¼Ã?e, Levin

on 2005-12-05 02:57

On 12/4/05, Levin A. <removed_email_address@domain.invalid> wrote: > (self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining) > end I don't really like multiple returns, which is why I wrote it like that. But the above is still pretty nice, and certainly more succinct. Here you can also see how similar this is to Rob L.'s method of finding the sums of the subsets. He posted before me though and deserves credit as well for a nice and fast solution. His solution is in the original quiz thread. Ryan

on 2005-12-05 04:30

I have a solution for the "effectively useless" basket. It's a naive algorithm, and I haven't yet received a number above 70 from it. The advantages are that it's straightforward idiomatic Ruby, and core of the algorithm is expressed about as tersely as Martin's definition. And I like my ArraySubsetList class. class Fixnum def divisors (1..self).select {|i| self % i == 0 } end end module Enumerable def sum inject(0) {|m, o| m + o } end end class Array def subsets ArraySubsetList.new(self) end end class ArraySubsetList def initialize(array) @array = array end def [](index) return nil unless (0...size) === index ret = [] @array.size.times {|i| ret << @array[i] if index[i] == 1 } ret end def each size.times {|bits| yield self[bits] } end include Enumerable def size 1 << @array.size end alias length size end def wierd_numbers_up_to(max) ret = [] for n in 1..max # 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. divs = n.divisors divs.delete i if divs.sum > i && divs.subsets.select {|subset| subset.sum == i }.empty? ret << i yield i if block_given? end end ret end if $0 == __FILE__ if ARGV.size == 1 && (ARGV[0].to_i rescue 0) > 0 wierd_numbers_up_to(ARGV[0].to_i) {|n| puts n } else puts "usage: #$0 n\n Find all weird numbers less than n" end end Cheers, Dave

on 2005-12-05 06:29

Wow, I got a lot from looking at the other solutions. Thanks especially to Ed, Ryan, Jannis and Christian. I see that the single biggest performance gain comes from using a recursive sum_in_subset? method such as that found in Ed's solution. I've borrowed from his code for this fairly simple and straightforward resubmission. It doesn't perform as well as the faster solutions, but it's much, much faster than my first submission. #!/usr/bin/env ruby # # Ruby Q. Weird Numbers solution. # Uses recursive sum_in_subset? approach borrowed from # other solutions. # class Integer def weird? divisors = self.divisor_list abundancy = divisors.inject { |total,x| total += x } - self return false unless abundancy > 0 smalldivisors = divisors.reverse.select { |j| j <= abundancy } return false if sum_in_subset?(smalldivisors, abundancy) return true end def sum_in_subset?(list, target) return false if target < 0 return true if list.include?(target) return false if list.length == 1 first = list.first rest = list[1..-1] sum_in_subset?(rest, target-first) or sum_in_subset?(rest, target) end def divisor_list list = [] (1..Math.sqrt(self).to_i).each do |x| if self % x == 0 list << x list << (self / x) unless x == 1 or (self / x) == x end end return list.sort end end #################### unless ARGV.length == 1 puts "Usage: #{$0} <max_value>" end max_value = ARGV.shift.to_i (1..max_value).each { |n| puts n if n.weird? }

on 2005-12-05 08:18

Here's mine. I started out with very straightforward programming, but ended up making it muddier as I optimized. I also implemented a bunch of functions that I figured I could probably find alread written if I looked, but I figured they were good exercises : Integer#factors, Integer#divisors, Array#all_combinations.... I thought it was pretty fast, especially compared to my initial implementation. Then I timed Ryan's on my machine... Oh well. I enjoyed the challenge. -Adam --- class Integer def weird? (d = divisors).pop #remove self (which is always last) d.sum > self && !d.quick_find_subset_with_sum(self) && #weed out most !d.find_subset_with_sum(self) #confirm the rest end def divisors factors.all_combinations.uniq.inject([]){|result,combo| result << combo.product }.sort.uniq end def factors value, candidate = self, 3 factors = [1] while value % 2 == 0 factors << 2 value /= 2 end while candidate <= Math.sqrt(value) while value % candidate == 0 factors << candidate value /= candidate end candidate += 2 end factors << value if value != 1 factors end end class Array def product inject(1){|p,v| p*v} end def sum inject(0){|s,v| s+v} end def all_combinations ComboIndexGenerator.new(self.size).inject([]) {|result, index_set| result << values_at(*index_set) } end #this was my first attempt, which was straightforward, # but slow as heck for large sets def slow_find_subset_with_sum n return nil if sum < n all_combinations.each {|set| return set if set.sum == n } nil end #this is my second attempt which is fast but misses some subsets. #but it is useful for quickly rejecting many non-weird numbers. def quick_find_subset_with_sum n a = self.sort.reverse sum,set = 0,[] a.each {|e| if (sum+e <= n) sum+=e set<<e end return set if sum == n } nil end #this one works pretty quickly... #it never tests subsets which are less than the sum, #and keeps track of sets it has already calculated def find_subset_with_sum n possibilities, seen = [self],{} until possibilities.empty? candidate = possibilities.pop diff = candidate.sum - n return candidate if diff == 0 break if diff < 0 candidate.each_with_index{|e,i| break if e > diff new_cand = (candidate.dup) new_cand.delete_at(i) return new_cand if e == diff possibilities << new_cand if !seen[new_cand] seen[new_cand]=true } end nil end end #this class generates an all the possible combinations of n items #it returns an array with the next combination every time you call #next class ComboIndexGenerator include Enumerable def initialize nitems @n = nitems @max = 2**@n @val=0 end def to_a return nil if @val==@max (0..@n).inject([]){|a,bit| a<<bit if @val[bit]==1; a} end def next @val+=1 if @val<@max to_a end def each &b yield to_a while (n=self.next) yield n 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

on 2005-12-05 12:57

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

on 2005-12-08 10:48

```
I was impressed when I started going through 1..1000 in under 15
seconds, so this is much slower than others report. I'm just going to
tell myself you all have much faster computers, and go to bed.
require 'set'
class Subsets
def initialize(set, start)
@set = set.to_a.uniq.sort
@num_elements = start - 1
@map = {}
@set.each_with_index {|k, v| @map[k] = v+1}
end
# returns each subset, in turn. Returns nil when there are no more
def succ
if @combo == nil or @combo == @set[-@num_elements..-1]
return nil if (@num_elements +=1) > @set.length
@combo = @set[0,@num_elements]
else
index = (1..@num_elements).find {|i| @combo[-i] < @set[-i]}
@combo[-index, index] = @set[@map[@combo[-index]], index]
end
@combo
end
def find
while(x = succ)
break if yield x
end
x
end
end
class Integer
def proper_divisors
return [] if self < 2
div = Set.new [1]
2.upto(Math.sqrt(Float.induced_from(self)).to_i) {|i|
quotient, modulus = self.divmod(i)
div.merge([i,quotient]) if modulus.zero?
}
div.to_a.sort
end
def abundant?
self > 11 and [0].concat(proper_divisors).inject {|sum,n| sum += n}
> self
end
def semiperfect?
return nil if self < 6
subsets = Subsets.new(proper_divisors, 2)
subsets.find {|subset| [0].concat(subset).inject {|sum,n| sum += n}
== self }
end
def weird?
self > 69 and abundant? and not semiperfect?
end
end
n = gets.strip
exit if n =~ /\D/ or n !~ /[^0]/
p (1..n.to_i).find_all {|i| i.weird? }
```