[QUIZ] Weird Numbers (#57)

[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 =3D []
i =3D 1
while i*i < self
if self % i =3D=3D 0
res << i
end
i +=3D 1
end
(res.size - 1).downto(1) do |k|
res << self / res[k]
end
res << i if i*i =3D=3D self
res
end
end

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

divisors =3D n.divisors

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

return false if div_sum <=3D n

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

divisors.each do |i|
possible_sums.keys.sort.each do |s|
new_sum =3D s + i
case new_sum <=3D> diff
when -1
possible_sums[new_sum] =3D true
when 0
return false
when 1
break
end
end
end

return true
end

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

 

[Dan Diebolt]

--0-2093205057-1134037176=:9340
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable

I found this program msieve.exe that does Quadratic Seive Factoring of ar=
bitrary integers and I wonder if there is time enough to put together a b=
rute force solution to the Weird Number quiz before the summary comes out=
The basic idea would be to find the prime factors of successive integer=
s using the output msieve.exe and testing for abundance and weirdness bas=
ed on these factors. Is there any rule on the Quiz the prevents helper co=
des from being used? The Quadratic Seive is the fastest algorithm known f=
or 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.
=20
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=
:
=20
irb(main):010:0> puts `msieve -q 2138723987`
2138723987
p2: 29
p2: 37
prp7: 1993219
=3D> nil
=20
check: 2_138_723_987 =3D 29 * 37 * 1_993_219
=20
Here is the program:
=20
http://www.boo.net/~jasonp/qs.html
=20
and here is a summary of the theory:
=20
http://en.wikipedia.org/wiki/Quadratic_sieve
=20
Here are the switches for controlling msieve:
=20
msieve -h displays command options:
=20
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
=20
Here is a list of 15 million prime numbers that might be helpful checki=
ng computations:
=20
http://primes.utm.edu/lists/small/millions/

=09

 

[James Edward Gray II]

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]

--HcAYCG3uE/tztfnV
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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.=20

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

--HcAYCG3uE/tztfnV
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDmER3nhUz11p9MSARApN+AKC2mwH+eNXtfA9B3UTOlPNbNmHCWwCg5Idl
USoJaw4gTk/KMLWknEhKQ7o=
=kOLW
-----END PGP SIGNATURE-----

--HcAYCG3uE/tztfnV--