Counting Carmichael numbers with small seeds

Abstract:

Let $A_s$ be the product of the first $s$ primes, let $\mathcal {P}_s$ be the set of primes $p$ for which $p-1$ divides $A_s$ but $p$ does not divide $A_s$, and let $\mathcal {C}_s$ be the set of Carmichael numbers $n$ such that $n$ is composed entirely of the primes in $\mathcal {P}_s$ and such that $A_s$ divides $n-1$. Erdős argued that, for any $\varepsilon >0$ and all sufficiently large $x$ (depending on the choice of $\varepsilon$), the set $\mathcal {C}_s$ contains more than $x^{1-\varepsilon }$ Carmichael numbers $\leq x$, where $s$ is the largest number such that the $s$th prime is less than $\ln x^{\varepsilon /4}$. Based on Erdős’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 $|\mathcal {C}_s|$ grows rapidly on $s$: $|\mathcal {C}_s|=2^{2^{s(1-\varepsilon )}}$ with $\lim _{s\rightarrow \infty } \varepsilon =0,$ or, equivalently, $|\mathcal {C}_s|=A_s^{2^{s(1-\varepsilon ’)}}$ with $\lim _{s\rightarrow \infty } \varepsilon ’=0$. We describe a procedure to compute exact values of $|\mathcal {C}_s|$ for small $s$. In particular, we find that $|\mathcal {C}_9|=8,281,366,855,879,527$ with $\varepsilon =0.36393\ldots$ and that $|\mathcal {C}_{10}|=21,823,464,288,660,480,291,170,614,377,509,316$ with $\varepsilon =0.31662\ldots$. The entire calculation for computing $|\mathcal {C}_s|$ for $s\leq 10$ took about 1,500 hours on a PC Pentium Dual E2180/2.0GHz with 1.99 GB memory and 36 GB disk space.