An interesting observation
- -----BEGIN PGP SIGNED MESSAGE-----
I was trying to work out the complexity of the ``sieving for smooth numbers''
technique, employed for instance in the Quadratic Sieve algorithm. A
reference is C&P section 3.2.5. The number of positions marked by this sieve,
when applied over an array of n elements, is n/p_1 + n/p_2 + n/p_3 + ...,
with p_i ranging over all prime _powers_ up to a bound B.
A well-known result (C&P Theorem 1.4.2, Hardy and Wright Theorem 427 for a
proof) states that the partial sum of reciprocals of primes (up to B) is
asymptotic to log log B. Thus, if the algorithm searched for squarefree
B-smooth numbers only, this result asserts that the complexity of the
algorithm would be O(n log log B). Interestingly enough, the sum of
reciprocals of prime powers p^a with a>1 converges to 0.773156669..., leaving
that bound unchanged if the prime powers are included.
So if one is already sieving for the primes, then sieving for prime powers is
performed ``for free'' (asymptotically speaking). An interesting result, in
my opinion, and I thought that I'd share with you.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
-----END PGP SIGNATURE-----