COUNTING CARMICHAEL NUMBERS WITH SMALL SEEDS

Let A(s) be the product of the first s primes, let P(s) be the set of primes p for which p - 1 divides A(s) but p does not divide A(s), and let C(s) be the set of Carmichael numbers n such that n is composed entirely of the primes in P(s) and such that A(s) divides n - 1. Erdos argued that, for any epsilon > 0 and all sufficiently large x (depending on the choice of epsilon), the set C(s) contains more than x(1-epsilon) Carmichael numbers <= x, where s is the largest number such that the sth prime is less than ln x(epsilon/4). Based on Erdos's original heuristic, though with certain modification, Alford, Granville, and Pomerance proved that there are more than x(2/7) Carmichael numbers up to x, once x is sufficiently large. The main purpose of this paper is to give numerical evidence to support the following conjecture which shows that vertical bar C(s)vertical bar grows rapidly on s: vertical bar C(s)vertical bar = 2(2s(1 - epsilon)) with lim(s ->infinity) epsilon = 0, or, equivalently, vertical bar C(s)vertical bar = A(s)(2s(1-epsilon)'())) with lim(s ->infinity) epsilon' = 0. We describe a procedure to compute exact values of 1051 for small s. In particular, we find that vertical bar C(9)vertical bar = 8, 281,366, 855,879, 527 with epsilon = 0.36393... and that vertical bar C(10)vertical bar = 21, 823, 464, 288, 660, 480, 291, 170, 614, 377, 509, 316 with epsilon = 0.31662.... The entire calculation for computing vertical bar C(s)vertical bar for s <= 10 took about 1,500 hours on a PC Pentium Dual E2180/2.0GHz with 1.99 GB memory and 36 GB disk space.