Reply to thread

Message: [QUOTE="Edward Faulkner, post: 4495110"] --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] [/QUOTE]

Verification