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?