Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Counting Carmichael numbers with small seeds

Author: Zhenxiang Zhang
Journal: Math. Comp. 80 (2011), 437-442
MSC (2010): Primary 11Y16, 11Y35; Secondary 11Y11
Published electronically: July 19, 2010
MathSciNet review: 2728989
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \vert\mathcal{C}_s\vert$ grows rapidly on $ s$: $ \vert\mathcal{C}_s\vert=2^{2^{s(1-\varepsilon)}}$ with $ \lim_{s\rightarrow \infty} \varepsilon=0,$ or, equivalently, $ \vert\mathcal{C}_s\vert=A_s^{2^{s(1-\varepsilon')}}$ with $ \lim_{s\rightarrow \infty} \varepsilon'=0$. We describe a procedure to compute exact values of $ \vert\mathcal{C}_s\vert$ for small $ s$. In particular, we find that $ \vert\mathcal{C}_9\vert=8,281,366,855,879,527$ with $ \varepsilon=0.36393\ldots$ and that $ \vert\mathcal{C}_{10}\vert=21,823,464,288,660,480,291,170,614,377,509,316$ with $ \varepsilon=0.31662\ldots$. The entire calculation for computing $ \vert\mathcal{C}_s\vert$ 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11Y35, 11Y11

Retrieve articles in all journals with MSC (2010): 11Y16, 11Y35, 11Y11

Additional Information

Zhenxiang Zhang
Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, People’s Republic of China

Keywords: Carmichael numbers (with small seeds), Korselt’s criterion, heuristics of Erdős-AGP concerning Erdős’s construction of Carmichael numbers, product of the first $s$ primes, algorithms
Received by editor(s): October 19, 2009
Received by editor(s) in revised form: October 28, 2009
Published electronically: July 19, 2010
Additional Notes: The author was supported by the NSF of China Grant 10071001.
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society