On the distribution of Carmichael numbers

Aran Nayebi

Published 2009-06-19, updated 2013-11-12Version 22

Erd\H{o}s conjectured in 1956 that there are $x^{1-o(1)}$ Carmichael numbers up to $x$. Pomerance made this conjecture more precise and proposed that there are $x^{1-{\frac{\{1+o(1)\}\log\log\log x}{\log\log x}}}$ Carmichael numbers up to $x$. At the time, his data tables up to $25 \cdot 10^{9}$ appeared to support his conjecture. However, Pinch extended this data and showed that up to $10^{21}$, Pomerance's conjecture did not appear well-supported. Thus, the purpose of this paper is two-fold. First, we build upon the work of Pomerance and others to present an alternate conjecture regarding the distribution of Carmichael numbers that fits proven bounds and is better supported by Pinch's new data. Second, we provide another conjecture concerning the distribution of Carmichael numbers that sharpens Pomerance's heuristic arguments. We also extend and update counts pertaining to pseudoprimes and Carmichael numbers, and discuss the distribution of One-Parameter Quadratic-Base Test pseudoprimes.