Counting Carmichael numbers with small seeds

Author:
Zhenxiang Zhang

Journal:
Math. Comp. **80** (2011), 437-442

MSC (2010):
Primary 11Y16, 11Y35; Secondary 11Y11

DOI:
https://doi.org/10.1090/S0025-5718-2010-02382-8

Published electronically:
July 19, 2010

MathSciNet review:
2728989

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be the product of the first primes, let be the set of primes for which divides but does not divide , and let be the set of Carmichael numbers such that is composed entirely of the primes in and such that divides . Erdős argued that, for any and all sufficiently large (depending on the choice of ), the set contains more than Carmichael numbers , where is the largest number such that the th prime is less than . Based on Erdős's original heuristic, though with certain modification, Alford, Granville, and Pomerance proved that there are more than Carmichael numbers up to , once is sufficiently large.

The main purpose of this paper is to give numerical evidence to support the following conjecture which shows that grows rapidly on : with or, equivalently, with . We describe a procedure to compute exact values of for small . In particular, we find that with and that with . The entire calculation for computing for took about 1,500 hours on a PC Pentium Dual E2180/2.0GHz with 1.99 GB memory and 36 GB disk space.

**1.**W. R. Alford, A. Granville, and C. Pomerance,*There are infinitely many Carmichael numbers*, Annals of Math.**140**(1994), 703-722. MR**1283874 (95k:11114)****2.**R. D. Carmichiael,*Note on a new number theory function*, Bull. A. M. S.**16**(1910), 232-238. MR**1558896****3.**R. Crandall and C. Pomerance,*Prime numbers, a computational perspective*, 2nd ed., Springer-Verlag, New York, 2005. MR**2156291 (2006a:11005)****4.**P. Erdős,*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201-206. MR**0079031 (18:18e)****5.**A. Granville,*Primality testing and Carmichael numbers*, Notices of the American Mathematical Society**39**(1992), 696-700.**6.**A. Korselt,*Problème chinois*, L'intermédiaire des mathématiciens**6**(1899), 142-143.**7.**Richard G. E. Pinch,*The Carmichael numbers up to*, in Proceedings of Conference on Algorithmic Number Theory 2007 (edited by Anne-Maria Ernvall-Hytönen, Matti Jutila, Juhani Karhumäki and Arto Lepistö), Turku Centre for Computer Science General Publication**46**(2007), 129-131.`http://tucs.fi/publications/insight.php?id=pErJuKaLe07a&table=proceeding`

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

Email:
zhangzhx@mail.wh.ah.cn, ahnu_zzx@sina.com

DOI:
https://doi.org/10.1090/S0025-5718-2010-02382-8

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.