From: Edward Faulkner <ef@...>
Date: 2005-12-05T04:15:55+09:00
Subject: Re: [QUIZ] Weird Numbers (#57) Solution

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