[Zhang 2011] Counting Carmichael numbers with small seeds,  Mathematics of Computation, 80:273 (2011),  437-442. 

 

ABSTRACT. Let  As be the product of the first s primes, let Ps be the set of  primes p for which p−1 divides As but p does not divide As , and let Cs be the  set of Carmichael numbers n such that n is composed entirely of the primes in Ps and such that As divides n − 1.  ErdÖs argued that, for any ε > 0 and all sufficiently large x (depending on the choice of ε),  the set Cs contains more than x 1−ε Carmichael numbers ≤ x, where s is the largest number such that the sth prime is less than ln xε/4. Based on ErdÖs’s original heuristic, though with certain modification, Alford, Granville, and Pomerance proved that there are more than x2/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 |Cs| grows rapidly on s:

(1)            log2 |Cs| = 2s(1−ε)

 

with lim s→∞ ε = 0. We describe a procedure to compute exact values of  |Cs|  for small s. In particular, we find that

|C9| = 8, 281, 366, 855, 879, 527 with ε = 0.36393 ...

and that

|C10|  = 21, 823, 464, 288, 660, 480, 291, 170, 614, 377, 509, 316  

with ε = 0.31662 ....

The entire calculation for computing |Cs|  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.

(Note that the counts of the number of Carmichael numbers in either ErdÖs’s conjecture or  AGP’s  theorem are functions which grow slowly on x For x = 10n for n up to 21 (which is as far as has been computed by Pinch), there are fewer than x0.348 Carmichael numbers up to x.)

Remark 1.1. Alford  took L = 26 ・ 33 ・ 52 ・ 72 ・ 11, determined 155 primes p for which p − 1 divides L, and then established that there are at least 2128 − 1 Carmichael numbers made up from them. However, Alford did not express the number of Carmichael numbers as a function of L. Granville mentioned: “It can be shown that if L = As for some sufficiently large s, then we can obtain more than 2 ln3 L primes in Ps, and so we’d expect more than

(2)           L ln2 L

Carmichael numbers in Cs.”   The estimate  (2)  seems to be the only estimate for  |Cs| in the literature, which grows much more slowly than that in Conjecture  (1).