Forum: Ruby Weird Numbers (#57) Solution

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
hcatlin (Guest)
on 2005-12-04 15:28
(Received via mailing list)
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
neoneye (Guest)
on 2005-12-04 16:29
(Received via mailing list)
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)
James G. (Guest)
on 2005-12-04 17:47
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-04 18:03
(Received via mailing list)
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.
levin (Guest)
on 2005-12-04 18:32
(Received via mailing list)
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
chneukirchen (Guest)
on 2005-12-04 18:56
(Received via mailing list)
#!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__
leavengood (Guest)
on 2005-12-04 19:13
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-04 19:29
(Received via mailing list)
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}
leavengood (Guest)
on 2005-12-04 19:34
(Received via mailing list)
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
Jay A. (Guest)
on 2005-12-04 19:38
(Received via mailing list)
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
neoneye (Guest)
on 2005-12-04 19:46
(Received via mailing list)
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.
leavengood (Guest)
on 2005-12-04 20:10
(Received via mailing list)
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
jannis (Guest)
on 2005-12-04 20:22
(Received via mailing list)
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__
ef (Guest)
on 2005-12-04 21:19
(Received via mailing list)
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
James G. (Guest)
on 2005-12-04 21:40
(Received via mailing list)
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
Kenneth C. (Guest)
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? }
leavengood (Guest)
on 2005-12-04 22:41
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-04 22:45
(Received via mailing list)
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 ]
hcatlin (Guest)
on 2005-12-04 22:53
(Received via mailing list)
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.
James G. (Guest)
on 2005-12-04 22:57
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-04 23:01
(Received via mailing list)
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.
James G. (Guest)
on 2005-12-04 23:01
(Received via mailing list)
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
leavengood (Guest)
on 2005-12-04 23:01
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-04 23:10
(Received via mailing list)
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.
leavengood (Guest)
on 2005-12-04 23:14
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-04 23:30
(Received via mailing list)
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.
leavengood (Guest)
on 2005-12-04 23:51
(Received via mailing list)
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
dandiebolt (Guest)
on 2005-12-04 23:59
(Received via mailing list)
> 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.
James G. (Guest)
on 2005-12-05 00:28
(Received via mailing list)
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
Christer N. (Guest)
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
leavengood (Guest)
on 2005-12-05 01:25
(Received via mailing list)
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
martindemello (Guest)
on 2005-12-05 02:21
(Received via mailing list)
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
levin (Guest)
on 2005-12-05 02:30
(Received via mailing list)
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
leavengood (Guest)
on 2005-12-05 02:57
(Received via mailing list)
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
dave (Guest)
on 2005-12-05 04:30
(Received via mailing list)
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
Kenneth C. (Guest)
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? }
adam.shelly (Guest)
on 2005-12-05 08:18
(Received via mailing list)
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
ruby.brian (Guest)
on 2005-12-05 12:57
(Received via mailing list)
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
Zed L. (Guest)
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? }
This topic is locked and can not be replied to.