Re: [QUIZ] Weird Numbers (#57)

[Brian Schröder]

On 02/12/05, Ruby Quiz <ja...@grayproductions.net> wrote:
> The three rules of Ruby Quiz:
>
> 1. Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3. Enjoy!
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Martin DeMello
>
> 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.
>
> Write a program to find all the weird numbers less than a given input.
>
>

I imagine that 1 is also excluded as a divisor, otherwise the answer
would be the empty set always.

Brian

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

[Ruby Quiz]

[Brian Schröder]

On 02/12/05, Brian Schröder <ruby....@gmail.com> wrote:
> On 02/12/05, Ruby Quiz <ja...@grayproductions.net> wrote:
> > The three rules of Ruby Quiz:
> >
> > 1. Please do not post any solutions or spoiler discussion for this quiz until
> > 48 hours have passed from the time on this message.
> >
> > 2. Support Ruby Quiz by submitting ideas as often as you can:
> >
> > http://www.rubyquiz.com/
> >
> > 3. Enjoy!
> >
> > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> >
> > by Martin DeMello
> >
> > 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.
> >
> > Write a program to find all the weird numbers less than a given input.
> >
> >
>
> I imagine that 1 is also excluded as a divisor, otherwise the answer
> would be the empty set always.
>
> Brian

Sorry for the noise...

[JB Eriksson]

please give an example of such a number. english is my second language, and
english math speak is more like my sixth language or so (below
german,swedish techspeak and english techspeak).

[Kroeger, Simon (ext)]

If I got I right, 70 would be such a number.
(I hope this is no spoiler)

divisors = [1, 2, 5, 7, 10, 14, 35]
sum = 74

no combination of the divisors adds up to 70

cheers

Simon

[Warren Brown]

JB,

> please give an example of such a number. english is my
> second language, and english math speak is more like

> my sixth language or so (below german, Swedish
> techspeak and english techspeak).

Just Google for "weird number" and you will see lots of examples and
explanations.

- Warren Brown

[JB Eriksson]

I'm sorry, my google was broken O_o

seriously though, the lengthier an assignment is, the less misunderstanding
you get. Never having heard of weird numbers before, I thought it was
something made up by the quiz author.

[Dan Diebolt]

>please give an example of such a number.

70,836,4030,5830,7192,7912,9272,10430,10570,10792,10990,
11410,11690,12110,12530,12670,13370,13510,13790,13930,14770,
15610,15890,16030,16310,16730,16870,17272,17570,17990,18410,
18830,18970,19390,19670

On-Line Encyclopedia of Integer Sequences!
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006037

See Also:

http://en.wikipedia.org/wiki/Weird_number
http://mathworld.wolfram.com/WeirdNumber.html

I would like to see an iterator in Ruby that took as one of its arguments the On-Line Encyclopedia of Integer Sequences identifier (A006037). And also an iterator in Ruby for the Combinatorial Object Server:

Combinatorial Object Server
http://www.theory.cs.uvic.ca/~cos/cos.html

Is that possible in Ruby?

---------------------------------
Yahoo! Personals
Skip the bars and set-ups and start using Yahoo! Personals for free

[Dan Diebolt]

If you download the Mathematica notebook file for "Weird Number" from this site:

http://mathworld.wolfram.com/WeirdNumber.html

You can convert the notebook file to pdf with this utility:

http://library.wolfram.com/Explore/Publishing/NBtoPDF.jsp

---------------------------------
Yahoo! Shopping
Find Great Deals on Gifts at Yahoo! Shopping

[Hampton]

Meh. I've done it (dont' worry, not posting it...), but this thing's
gotta be like O(n^3) at least.

-hampton.

[James Edward Gray II]

On Dec 3, 2005, at 10:47 AM, Hampton wrote:

> Meh. I've done it (dont' worry, not posting it...), but this thing's
> gotta be like O(n^3) at least.

When this quiz was posed to me, the creator thought it would be
interesting to see what optimizations people came up with. Now,
watching the discussions since it has released, I have an idea for
another hefty one. Think outside the box... ;)

James Edward Gray II

[Hampton]

I have a feeling we have the same idea.

-hampton.

[James Edward Gray II]

On Dec 3, 2005, at 12:37 PM, Hampton wrote:

> I have a feeling we have the same idea.

Code it up and send it in tomorrow. I'll create my idea if I don't
see a match for it...

James Edward Gray II

[Nate]

Dan Diebolt wrote:
> >please give an example of such a number.
>
> 70,836,4030,5830,7192,7912,9272,10430,10570,10792,10990,
> 11410,11690,12110,12530,12670,13370,13510,13790,13930,14770,
> 15610,15890,16030,16310,16730,16870,17272,17570,17990,18410,
> 18830,18970,19390,19670
>

I can see how 70 is a "weird number" (divisors 2 + 5 + 7 + 10 + 14 + 35
= 74 and no subset adds up to 70), but can someone explain to me how
836 is considered "weird"?

2 + 11 + 19 + 22 + 38 + 209 = 301

Am I missing a divisor, because last time I checked 301 < 836. When I
factor 836, I come up with 2 * 2 * 11 * 19 = 836. Is this just one of
those cases where the internet is *wrong*?

Very confused,

-Nate

[James Edward Gray II]

On Dec 3, 2005, at 5:22 PM, Nate wrote:

> When I factor 836, I come up with 2 * 2 * 11 * 19 = 836.

You're using the same factor twice in there. That doesn't seem right...

James Edward Gray II

[Simon Kröger]

erm, if 2 is a divisor 836/2=418 should also be, hmm?

get some sleep :)

(and you missed some more: 1, 4, 38, 44, 76)

cheers

Simon

[Nathan]

James Edward Gray II wrote:
> On Dec 3, 2005, at 5:22 PM, Nate wrote:
>
> > When I factor 836, I come up with 2 * 2 * 11 * 19 = 836.
>
> You're using the same factor twice in there. That doesn't seem right...
>

True, the only factors of 836 are 2, 11, and 19. I just meant to point
out that those are definitely the only factors because 2^2 * 11^1 *
19^1 = 836. That said, does 836 have any other divisors besides 2, 11,
19, 22, 38, and 209? I don't see how it could, but I would love to be
proved wrong.

Mostly I just want to know if the list posted previously is accurate or
not.

[Nathan]

Ah ha. That's exactly what I was looking for.

Thanks!

[Paolo Capriotti]

On 12/4/05, Nathan <nmo...@gmail.com> wrote:
>
> True, the only factors of 836 are 2, 11, and 19. I just meant to point
> out that those are definitely the only factors because 2^2 * 11^1 *
> 19^1 = 836. That said, does 836 have any other divisors besides 2, 11,
> 19, 22, 38, and 209? I don't see how it could, but I would love to be
> proved wrong.

irb(main):001:0> (1..836).select{|d| 836 % d == 0}
=> [1, 2, 4, 11, 19, 22, 38, 44, 76, 209, 418, 836]

> Mostly I just want to know if the list posted previously is accurate or
> not.

I think it is.

Paolo

[Nathan]

Paolo Capriotti wrote:
> On 12/4/05, Nathan <nmo...@gmail.com> wrote:
>
> irb(main):001:0> (1..836).select{|d| 836 % d == 0}
> => [1, 2, 4, 11, 19, 22, 38, 44, 76, 209, 418, 836]

Simon's right. I definitely need more sleep.

Cheers,

-Nathan

[Rob Leslie]

My first Ruby Quiz solution...

Cheers,
-rob

#! /usr/bin/ruby
#
# Ruby program to find all the weird numbers less than a given input
# Rob Leslie <r...@mars.org>
#

class Integer
WEIRD_ODD_UNKNOWN_THRESHOLD = 10 ** 18

def weird?
# Odd numbers less than 10**18 are not weird. (Bob Hearn, July
2005)
return false if self & 1 == 1 && self < WEIRD_ODD_UNKNOWN_THRESHOLD

# Weird numbers are abundant. To be abundant, the sum of the
divisors
# must be greater than twice this number. Equivalently, the sum of
# the proper divisors (excluding the number itself) must be greater
# than this number.
divisors = self.divisors
sum = divisors.inject { |sum, x| sum + x } - self
return false unless sum > self

# Weird numbers are not semiperfect. To be semiperfect, the sum
of a
# subset of the divisors must be equal to this number.
Equivalently,
# the sum of another subset (the complement set) of divisors
must be
# equal to the difference between this number and the sum of all
its
# divisors.
excess = sum - self
addends = divisors.reject { |x| x > excess }
sum = addends.inject { |sum, x| sum + x }

# Trivially semiperfect or non-semiperfect?
return false if sum == excess || addends.include?(excess)
return true if sum < excess

# Default non-semiperfect test (with special case speed
optimization)
self < 222_952 ? 9_272 == self : !excess.sum_of_subset?(addends)
end

def divisors
# Naive implementation; OK for small numbers
list = (1..Math.sqrt(self).floor).select { |i| (self % i).zero? }
list + list.reverse.collect { |i| self / i }
end

def sum_of_subset?(addends)
first = addends.first
return true if self == first
return false unless addends.length > 1
rest = addends[1..-1]
(self - first).sum_of_subset?(rest) or self.sum_of_subset?(rest)
end
end

input = ARGV.shift.to_i

70.upto(input - 1) do |number|
puts number if number.weird?
end

[Rob Leslie]

And immediately upon posting my first Ruby Quiz solution, I
discovered a small bug. :-{

Perhaps someone will notice it. :-)

--
Rob Leslie
r...@mars.org

[Hampton]

This thread was getting a little crowded, so I started a new one for
solutions.

[James Edward Gray II]

On Dec 2, 2005, at 9:31 AM, Dan Diebolt wrote:

> I would like to see an iterator in Ruby that took as one of its
> arguments the On-Line Encyclopedia of Integer Sequences identifier
> (A006037). And also an iterator in Ruby for the Combinatorial
> Object Server:
>
> Combinatorial Object Server
> http://www.theory.cs.uvic.ca/~cos/cos.html
>
> Is that possible in Ruby?

You bet. Use the openuri library to grab the page, parse out what
you need, and yield results. It's not even hard. Give it a try and
you'll learn a lot about Ruby... ;)

James Edward Gray II

[Dan Diebolt]

I am not talking about screen scraping bits and pieces of information off web sites but rather having a library of combinatorial iterators wrapped up in classes: Combinations, Permutations, ... Debruijn Sequences. Ruby blocks & yield statements would be a great way to process each element of the combinatorial structure seperating the problems of 1) generating the next element of combinatorial structure from 2) processing each element of the combinatorial structure.

James Edward Gray II

---------------------------------
Yahoo! Personals
Single? There's someone we'd like you to meet.
Lots of someones, actually. Yahoo! Personals

[Paolo Capriotti]

On 12/4/05, Rob Leslie <r...@mars.org> wrote:
> And immediately upon posting my first Ruby Quiz solution, I
> discovered a small bug. :-{
>
> Perhaps someone will notice it. :-)

I've found this one:

$ irb -r weird.rb
irb(main):001:0> 4.divisors
=> [1, 2, 2, 4]

:)

Paolo

[Paolo Capriotti]

This is my solution:

class Integer
def divisors
res = []
i = 1
while i*i < self
if self % i == 0
res << i
end
i += 1
end
(res.size - 1).downto(1) do |k|
res << self / res[k]
end
res << i if i*i == 0
res
end
end

def weird(n)
div_sum = 0
possible_sums = Hash.new
possible_sums[0] = true

n.divisors.each do |i|
div_sum += i

possible_sums.keys.each do |s|
new_sum = s + i
possible_sums[new_sum] = true if new_sum <= n
return false if new_sum == n
end
end

return div_sum > n
end

n = ARGV.shift or exit
n = n.to_i
m = ARGV.shift
m = m.to_i if m
range = m ? (n..m) : (1..n)
for i in range
puts i if weird(i)
end

--
Paolo

[Rob Leslie]

On Dec 4, 2005, at 9:03 AM, Paolo Capriotti wrote:
>> And immediately upon posting my first Ruby Quiz solution, I
>> discovered a small bug. :-{
>>
>> Perhaps someone will notice it. :-)
>
> I've found this one:
>
> $ irb -r weird.rb
> irb(main):001:0> 4.divisors
> => [1, 2, 2, 4]
>
> :)

Exactly right. :-)

I had previously written Integer#divisors something like this:

def divisors
list = (2..Math.sqrt(self).floor).select { |i| (self % i).zero? }
list += list.collect { |i| self / i }
[1, *list].uniq
end

but forgot the value of calling Array#uniq upon simplifying and
refactoring.

--
Rob Leslie
r...@mars.org

[Mike Harris]

My solution. Error checking is minimal to nonexistent.

class Integer
def each_divisor
for i in 1...self
yield(i) if self%i == 0
end
end

def weird?
sum = 0
each_divisor do |i| sum += i end
return false if sum <= self
each_divisor do |i|
return false if sum-i == self
end
end
end

print "Enter Number (Program will print all lesser weird numbers): "
num = gets
for i in 1...num.to_i
puts i if i.weird?
end

[James Edward Gray II]

On Dec 5, 2005, at 9:38 AM, Mike Harris wrote:

> each_divisor do |i|
> return false if sum-i == self
> end

Hmm, does that work?

I'm not trying to slander your code. I'm actually asking because I
think it's very elegant, if it's also correct.

You're code removes divisors one-by-one, but what if our divisors
looked something like:

1, ..., 50, ..., 100

And the total sum was just 50 over the number we're testing? The
order we remove divisors might be significant then. Am I right?

James Edward Gray II

[Bob Showalter]

Here's my solution, made before peeking at any of the other submissions.
It's not too bad; generates the weird numbers up to 100,000 in about 3
minutes on a pokey 233 Celeron.

http://users.adelphia.net/~showaltb/rubyquiz/57/weird.rb

Now I'm off to peek at the other solutions to see how bad my algorithm is!

[Mike Harris]

James Edward Gray II wrote:

ah, I screwed up and scrambled the problem description inbetween reading
it and writing it. My solution only considers subsets of size N-1,
where N is the divisor count.

[Mike Harris]

James Edward Gray II wrote:

looks like the proper way I should have done this is to define
Array#each_subset (or possibly Enumerable#each_subset) and cycle through
divisors.each_subset

[Ryan Leavengood]

Your solution is definitely in the faster group Bob, though about a
third as fast as the fastest (based on quick and dirty testing on my
laptop.)

In general your algorithm is pretty similar to the faster ones. You
know, it seems like it would be useful to analyze all the solutions to
possibly find Ruby "performance anti-patterns", since there are some
wildly different performance numbers in the solutions for this quiz.

If you think about it, people who complain about Ruby's performance
may just be using some of these "performance anti-patterns", and could
greatly increase performance with some knowledgeable tweaking. For
example the blogger who was analyzing his web server logs and
unnecessarily parsing a lot of dates, which slowed things down a lot.
When I politely corrected him on this and he changed the code,
performance greatly increased, and his view of Ruby improved a lot too
[1].

Ryan

1. http://www.pankaj-k.net/archives/2005/11/revised_ruby_or.html

[Moses Hohman]

This is my first ruby quiz solution since Quiz #1 : ) Thanks, it was
fun.

Moses

[Paolo Capriotti]

My previous solution contained an error. This is a new version,
corrected and slightly optimized, but still not quite as fast as the
fastest solutions.

Paolo

--

class Integer
def divisors
res = []
i = 1
while i*i < self
if self % i == 0
res << i
end
i += 1
end
(res.size - 1).downto(1) do |k|
res << self / res[k]
end

res << i if i*i == self
res
end
end

def weird(n)

possible_sums = Hash.new
possible_sums[0] = true

divisors = n.divisors

div_sum = divisors.inject(0) {|s, i| s+i }

return false if div_sum <= n

diff = div_sum - n
return false if divisors.include? diff

divisors.each do |i|
possible_sums.keys.sort.each do |s|

new_sum = s + i

case new_sum <=> diff
when -1
possible_sums[new_sum] = true
when 0
return false
when 1
break
end
end
end

return true

[Dan Diebolt]

I found this program msieve.exe that does Quadratic Seive Factoring of arbitrary integers and I wonder if there is time enough to put together a brute force solution to the Weird Number quiz before the summary comes out The basic idea would be to find the prime factors of successive integers using the output msieve.exe and testing for abundance and weirdness based on these factors. Is there any rule on the Quiz the prevents helper codes from being used? The Quadratic Seive is the fastest algorithm known for factoring integers with less than 110 digits. In the search for Weird Numbers the speed of the Quadratic Seive factoring of sufficiently large numbers will probably overcome the repeated system calls and text parsing of the output.

Here is the Ruby code that will factor 2_138_723_987 in the blink of an eye into a 2 two digit (p2 token) and a seven digit (prp7 token) factors:

irb(main):010:0> puts `msieve -q 2138723987`
2138723987
p2: 29
p2: 37
prp7: 1993219
=> nil

check: 2_138_723_987 = 29 * 37 * 1_993_219

Here is the program:

http://www.boo.net/~jasonp/qs.html

and here is a summary of the theory:

http://en.wikipedia.org/wiki/Quadratic_sieve

Here are the switches for controlling msieve:

msieve -h displays command options:

C:\DOCUME~1\OWNER\DESKTOP>msieve -h
Msieve v. 1.03
usage: MSIEVE [options] [one_number]
options:
-s <name> save intermediate results to <name>
instead of the default msieve.dat
-l <name> append log information to <name>
instead of the default msieve.log
-i <name> read one or more integers to factor from
<name> (default worktodo.ini) instead of
from the command line
-m manual mode: enter numbers via standard input
-q quiet: do not generate any log information,
only print any factors found
-d <min> deadline: if still sieving after <min>
minutes, shut down gracefully (default off)
-r <num> stop after finding <num> relations
-c client: only perform sieving
-v verbose: write log information to screen
as well as to logfile

Here is a list of 15 million prime numbers that might be helpful checking computations:

http://primes.utm.edu/lists/small/millions/

---------------------------------
Yahoo! Shopping
Find Great Deals on Holiday Gifts at Yahoo! Shopping

[Ruby Quiz]

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 Leavengood'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?

[James Edward Gray II]

On Dec 8, 2005, at 4:19 AM, Dan Diebolt wrote:

> I found this program msieve.exe that does Quadratic Seive Factoring
> of arbitrary integers and I wonder if there is time enough to put
> together a brute force solution to the Weird Number quiz before the

> summary comes out.

No. ;) But don't let that discourage you from playing with the
idea. Summaries are about my schedule. Solutions are about yours.
They're only loosely related.

> Is there any rule on the Quiz the prevents helper codes from being
> used?

Not at all. We're not much of a rules bunch.

James Edward Gray II

[Edward Faulkner]

On Thu, Dec 08, 2005 at 07:19:43PM +0900, Dan Diebolt wrote:
> I found this program msieve.exe that does Quadratic Seive Factoring
> of arbitrary integers and I wonder if there is time enough to put
> together a brute force solution to the Weird Number quiz before the

> summary comes out. The basic idea would be to find the prime factors

> of successive integers using the output msieve.exe and testing for
> abundance and weirdness based on these factors.

I'd be curious to see how it works out, but my guess is that it won't
speed things up much. My solution sieves for prime numbers too (using
the simpler Sieve of Eratosthenes), and that only takes a tiny
fraction of the running time. The computationally hard part is
proving non-semiperfect.

regards,
Ed