# Weird Numbers (#57)

**URL:** <https://www.ruby-forum.com/t/weird-numbers-57/96054>\
**Category:** Ruby\
**Created:** [December 8, 2005, 3:40pm UTC](https://www.ruby-forum.com/t/weird-numbers-57/96054 "2005-12-08T15:40:01Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 8, 2005, 3:40pm UTC](https://www.ruby-forum.com/t/weird-numbers-57/96054/1 "2005-12-08T15:40:01Z")

</div>

In reading through all the interesting solutions to this quiz, I noticed  
two  
things. Some solutions were easy to follow and have clever ways to do  
the work.  
Others were very fast, thanks to good optimizations. Let’s examine one  
of each.

First, here is Brian Schroeder’s complete solution (minus a line I  
removed):

```
#!/usr/bin/ruby

# Break early version, checking if a number is weird
def weird_number(n)
  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)

```

This code is not blazing fast, but it’s easy to follow and a unique  
approach.  
That’s worth a look, I think.

All the action is in weird\_number(), which just returns true or false to  
indicate if the passed argument is indeed weird. It begins by  
initializing an  
overall sum variable and a Hash for subset\_sums. Notice that 0 is added  
to  
subset\_sums here. We will look at that more in a bit. (All the values  
of this  
Hash are set to true, but they are really unused. Brian just wanted the  
unique  
property of Hash keys.)

The method then walks from 1 to the number, looking for divisors. When  
a  
divisor is found, it’s added to the sum and then added to each previous  
subset\_sum (or just 0 on the first occurrence). Each time a new  
subset\_sum is  
generated, the total is checked against the number itself. This allows  
the code  
to return an early false, when it finds a match.

If none of the subset\_sums short-circuited the process, a final check is  
made to  
ensure that the overall sum exceeds the number. When it does, a weird  
number is  
found.

The rest of Brian’s code is just argument parsing, the search through  
the range  
of numbers, and output. This is very simple stuff.

I might suggest one change and that would be that printing the numbers  
as they  
are found makes the wait a little less tedious, I think. That’s an easy  
fix.  
The last line of code can be switched to:

```
(1..max).each { |n| puts n if weird_number n }

```

Brian’s code needs over a minute to find the weird numbers from 1 to  
10,000.  
That’s the downside. If you want to do it faster, you have to find some  
shortcuts and some submitters found great ones.

Let’s switch gears to Ryan L.'s code, which can do the same  
calculation  
in under a second. It starts with a simple helper method:

```
class Array
  def sum
    inject(0) do |result, i|
      result + i
    end
  end
end

# ...

```

I assume the standard Ruby idiom for summation needs little  
introduction. Let’s  
move on to the heart of the algorithm:

```
# ...

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

```
  # ...

```

Finding out if a number is weird requires a fair amount of processing.  
We need  
all of the divisors (a lot of work to find on big numbers), subset sums  
for  
those divisors, etc. However, we know some things about weird numbers  
that can  
be tested faster. If less work rules out that process some of the time,  
it can  
add up to a big win.

First of all, there are no known odd weird numbers, so we might as well  
toss out  
half of the set right off the bat. (It’s possible there are some very  
large odd  
weird numbers, but we would have trouble calculating those anyway.)  
Going a  
step further, there are simple mathematical formulas to determine if a  
number is  
abundant or semi-perfect. We can use those to quickly eliminate many  
numbers,  
because weird numbers are always abundant and never semi-perfect. If we  
make it  
that far, we will still have to do the work, but that allows us to skip  
a good  
deal of numbers that would have cost us time.

```
  # ...

  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.uniq
  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

```
# ...

```

There are even shortcuts to be found in the work itself. The biggest is  
in  
calculating divisors. You can just find those between 1 and the square  
root of  
the number, then use those to get the rest. Also, when checking divisor  
sums,  
work with the big numbers first, to get totals closer to the actual  
number that  
may rule it out quickly.

Another interesting option, much debated in the quiz solution thread, is  
the  
ability to add a cache to the program. If a weird number is added to  
the cache  
when found, future queries can be lightning quick. Here’s a nice bit of  
code  
Ryan added just to shut me up about the merits of caching (a noble  
goal!):

```
# ...

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

```
# ...

```

Nothing tricky there. We just have a container for numbers with the  
ability to  
save it out to disk. You can see that it is reloaded upon creation.

Finally, here’s the code that ties all this together:

```
# ...

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

```

Notice the nice use of variable scoping there. The variable i is set to  
69  
before the cache is walked. (Another optimization. 70 is the first  
weird  
number, so we can safely skip anything before that.) Numbers in the  
cache will  
replace i, leaving it holding the highest known weird number. Then, if  
the  
limit is higher than that, the code only needs to calculate from there  
up.

I’ve barely scratched the surface of the solutions here. There were  
many more  
gems hidden in them. I do recommend browsing the source of the others  
for  
picking up new tricks.

My thanks to all who solved this problem, took my abuse about caching,  
and  
especially to Ryan for building what I pestered him for.

We have two back-to-back quizzes for all you gamers out there coming up  
next.  
First, Kalah anyone?