zbMATH — the first resource for mathematics

Counting Carmichael numbers with small seeds. (English) Zbl 1225.11161
Let \(A_s\) be the product of the first \(s\) primes (called seeds by the author), \({\mathcal P}_s\) the set of primes \(p\) for which \(p-1\) divides \(A_s\) but \(p\) does not divide \(A_s\), \({\mathcal C}_s\) 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\). The author gives numerical evidence for the conjecture: \[ |{\mathcal C}_s|=2^{2^{s(1-\varepsilon)}}, \lim_{s\to\infty}\varepsilon=0. \] This shows that \(|{\mathcal C}_s|\) grows rapidly with \(s\). He describes a procedure to compute exact values of \(|{\mathcal C}_s|\) for small \(s\).

11Y11 Primality
11Y16 Number-theoretic algorithms; complexity
11Y35 Analytic computations
PDF BibTeX Cite
Full Text: DOI
[1] W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703 – 722. · Zbl 0816.11005
[2] R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), no. 5, 232 – 238. · JFM 41.0226.04
[3] Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. · Zbl 1088.11001
[4] P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201 – 206. · Zbl 0074.27105
[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 \( 10^{21}\), 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.