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

I've got an optimization I haven't seen anyone else use yet.  My
solution is roughly 20% faster than Ryan's.

The trick is that any number of the form k*(2^m)*p where m > 1 and p
is a prime such that 2 < p < 2^(m+1) is semiperfect (according to
wikipedia).  This rules out many numbers, and its cheaper than a
thorough search of subsets.

#!/usr/bin/ruby

def weird(max)
primes =3D sieve(max*2)
70.step(max,2){|n|=20
puts n if weird?(n,primes)
}
end

def weird?(n,primes)
divs =3D divisors(n)
abund =3D divs.inject(0){|a,b| a+b} - n
return false if abund <=3D 0
return false if spfilter(n,primes)
return false if divs.include? abund
smalldivs =3D divs.reverse.select{|i| i < abund}
not sum_in_subset?(smalldivs,abund)
end

def sum_in_subset?(lst,n)
#p [lst,n]
return false if n < 0
return true if lst.include? n
return false if lst.size =3D=3D 1
first =3D lst.first
rest =3D lst[1..-1]
sum_in_subset?(rest, n-first) or sum_in_subset?(rest,n)
end

def divisors(n)
result =3D []
sr =3D Math.sqrt(n).to_i
(2 .. sr).each {|d|
if n.modulo(d) =3D=3D 0
result << d
end
}
return [1] if result.empty?
hidivs =3D result.map {|d| n / d }.reverse
if hidivs[0] =3D=3D result[-1]
[1] + result + hidivs[1..-1]
else
[1] + result + hidivs
end
end

def spfilter(n,primes)
m =3D 0
save_n =3D n
while n[0]=3D=3D0
m +=3D 1
n >>=3D 1
end
return false if m =3D=3D 0
low =3D 2
high =3D 1 << (m+1)
primes.each {|p|
return false if p > high
if p > low
return true if n%p =3D=3D 0
end
}
raise "not enough primes while checking #{save_n}"
end

# Sieve of Eratosthenes
def sieve(max_prime)
candidates =3D Array.new(max_prime,true)
candidates[0] =3D candidates[1] =3D false
2.upto(Math.sqrt(max_prime)) {|i|
if candidates[i]
(i+i).step(max_prime,i) {|j| candidates[j] =3D nil}
end
}
result =3D []
candidates.each_with_index {|prime, i| result << i if prime }
result
end

weird(ARGV[0].to_i)

regards,
Ed

--pWyiEgJYm5f9v55/
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)

iD8DBQFDk0A4nhUz11p9MSARAoNYAJwL019QJvPwSZKfz07Jb8YoVQE0HQCfcnNB
uYGSx5ixnDXq4k+7FqlvWJw=
=Wzc9
-----END PGP SIGNATURE-----

--pWyiEgJYm5f9v55/--

I've got an optimization I haven't seen anyone else use yet.  My
solution is roughly 20% faster than Ryan's.

The trick is that any number of the form k*(2^m)*p where m > 1 and p
is a prime such that 2 < p < 2^(m+1) is semiperfect (according to
wikipedia).  This rules out many numbers, and its cheaper than a
thorough search of subsets.

#!/usr/bin/ruby

def weird(max)
primes =3D sieve(max*2)
70.step(max,2){|n|=20
puts n if weird?(n,primes)
}
end

def weird?(n,primes)
divs =3D divisors(n)
abund =3D divs.inject(0){|a,b| a+b} - n
return false if abund <=3D 0
return false if spfilter(n,primes)
return false if divs.include? abund
smalldivs =3D divs.reverse.select{|i| i < abund}
not sum_in_subset?(smalldivs,abund)
end

def sum_in_subset?(lst,n)
#p [lst,n]
return false if n < 0
return true if lst.include? n
return false if lst.size =3D=3D 1
first =3D lst.first
rest =3D lst[1..-1]
sum_in_subset?(rest, n-first) or sum_in_subset?(rest,n)
end

def divisors(n)
result =3D []
sr =3D Math.sqrt(n).to_i
(2 .. sr).each {|d|
if n.modulo(d) =3D=3D 0
result << d
end
}
return [1] if result.empty?
hidivs =3D result.map {|d| n / d }.reverse
if hidivs[0] =3D=3D result[-1]
[1] + result + hidivs[1..-1]
else
[1] + result + hidivs
end
end

def spfilter(n,primes)
m =3D 0
save_n =3D n
while n[0]=3D=3D0
m +=3D 1
n >>=3D 1
end
return false if m =3D=3D 0
low =3D 2
high =3D 1 << (m+1)
primes.each {|p|
return false if p > high
if p > low
return true if n%p =3D=3D 0
end
}
raise "not enough primes while checking #{save_n}"
end

# Sieve of Eratosthenes
def sieve(max_prime)
candidates =3D Array.new(max_prime,true)
candidates[0] =3D candidates[1] =3D false
2.upto(Math.sqrt(max_prime)) {|i|
if candidates[i]
(i+i).step(max_prime,i) {|j| candidates[j] =3D nil}
end
}
result =3D []
candidates.each_with_index {|prime, i| result << i if prime }
result
end

weird(ARGV[0].to_i)

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

iD8DBQFDk0A4nhUz11p9MSARAoNYAJwL019QJvPwSZKfz07Jb8YoVQE0HQCfcnNB
uYGSx5ixnDXq4k+7FqlvWJw=
=Wzc9
-----END PGP SIGNATURE-----
```