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
- http://www.pankaj-k.net/archives/2005/11/revised_ruby_or.html
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 ii < 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 ii == 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
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
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:
Quadratic sieve - Wikipedia
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 save intermediate results to
instead of the default msieve.dat
-l append log information to
instead of the default msieve.log
-i read one or more integers to factor from
(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 deadline: if still sieving after
minutes, shut down gracefully (default off)
-r stop after finding 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:
The first fifty million primes
On Thu, Dec 08, 2005 at 07:19:43PM +0900, Dan D. 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
On Dec 8, 2005, at 4:19 AM, Dan D. 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 G. II