Estimating the counts of Carmichael and Williams numbers with small multiple seeds
HTML articles powered by AMS MathViewer
- by Zhenxiang Zhang PDF
- Math. Comp. 84 (2015), 309-337 Request permission
Abstract:
For a positive even integer $L$, let $\mathcal {P}(L)$ denote the set of primes $p$ for which $p-1$ divides $L$ but $p$ does not divide $L$, let $\mathcal {C}(L)$ denote the set of Carmichael numbers $n$ where $n$ is composed entirely of primes in $\mathcal {P}(L)$ and where $L$ divides $n-1$, and let $\mathcal {W}(L)\subseteq \mathcal {C}(L)$ denote the subset of Williams numbers, which have the additional property that $p+1 \mid n+1$ for each prime $p\mid n$. We study $|\mathcal {C}(L)|$ and $|\mathcal {W}(L)|$ for certain integers $L$. We describe procedures for generating integers $L$ that have more even divisors than any smaller positive integer, and we obtain certain numerical evidence to support the conjectures that $\log _2|\mathcal {C}(L)|=2^{s(1+o(1))}$ and $\log _2|\mathcal {W}(L)|=2^{s^{1/2-o(1)}}$ when such an “even-divisor optimal” integer $L$ has $s$ different prime factors. For example, we determine that $|\mathcal {C}(735134400)| > 2\cdot 10^{111}$. Last, using a heuristic argument, we estimate that more than $2^{24}$ Williams numbers may be manufactured from a particular set of $1029$ primes, although we do not construct any explicit examples, and we describe the difficulties involved in doing so.References
- L. Alaoglu and P. Erdös, On highly composite and similar numbers, Trans. Amer. Math. Soc. 56 (1944), 448–469. MR 11087, DOI 10.1090/S0002-9947-1944-0011087-2
- W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874, DOI 10.2307/2118576
- Kais Bouallègue, Othman Echi, and Richard G. E. Pinch, Korselt numbers and sets, Int. J. Number Theory 6 (2010), no. 2, 257–269. MR 2646757, DOI 10.1142/S1793042110002922
- John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
- R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), no. 5, 232–238. MR 1558896, DOI 10.1090/S0002-9904-1910-01892-9
- Zhuo Chen and John Greene, Some comments on Baillie-PSW pseudoprimes, Fibonacci Quart. 41 (2003), no. 4, 334–344. MR 2022413
- Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
- Pierre Dusart, The $k$th prime is greater than $k(\ln k+\ln \ln k-1)$ for $k\geq 2$, Math. Comp. 68 (1999), no. 225, 411–415. MR 1620223, DOI 10.1090/S0025-5718-99-01037-6
- Othman Echi, Williams numbers, C. R. Math. Acad. Sci. Soc. R. Can. 29 (2007), no. 2, 41–47 (English, with English and French summaries). MR 2367725
- P. Erdös, On highly composite numbers, J. London Math. Soc. 19 (1944), 130–133. MR 13381, DOI 10.1112/jlms/19.75_{P}art_{3}.130
- P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206. MR 79031
- A. Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society 39 (1992), 696–700.
- A. Korselt, Problème chinois, L’intermédiaire des mathématiciens 6 (1899), 142-143.
- Jean-Louis Nicolas, Répartition des nombres hautement composés de Ramanujan, Canadian J. Math. 23 (1971), 116–130. MR 274400, DOI 10.4153/CJM-1971-012-6
- C. Pomerance, Are there counter-examples to the Baillie-PSW primality test?, Dopo Le Parole aangeboden aan Dr. A. K. Lenstra (H. W. Lenstra, Jr., J. K. Lenstraand P. Van Emde Boas, eds.), Amsterdam, 1984.
- S. Ramanujan, Highly composite numbers [Proc. London Math. Soc. (2) 14 (1915), 347–409], Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI, 2000, pp. 78–128. MR 2280858
- G. Robin, Méthodes d’optimisation pour un problème de théorie des nombres, RAIRO Inform. Théor. 17 (1983), no. 3, 239–247 (French, with English summary). MR 743888, DOI 10.1051/ita/1983170302391
- Kenneth H. Rosen, Elementary number theory and its applications, 4th ed., Addison-Wesley, Reading, MA, 2000. MR 1739433
- H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133–143. MR 447099, DOI 10.4153/CMB-1977-025-9
- Zhenxiang Zhang, A one-parameter quadratic-base version of the Baillie-PSW probable prime test, Math. Comp. 71 (2002), no. 240, 1699–1734. MR 1933051, DOI 10.1090/S0025-5718-02-01424-2
- Zhenxiang Zhang, Counting Carmichael numbers with small seeds, Math. Comp. 80 (2011), no. 273, 437–442. MR 2728989, DOI 10.1090/S0025-5718-2010-02382-8
Additional Information
- Zhenxiang Zhang
- Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, People’s Republic of China
- Email: ahnu_zzx@sina.com, ahnu_zzx@sohu.com
- Received by editor(s): June 26, 2012
- Received by editor(s) in revised form: January 6, 2013, April 8, 2013, and May 1, 2013
- Published electronically: April 8, 2014
- Additional Notes: The author was supported by the NSF of China, Grant 10071001.
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 84 (2015), 309-337
- MSC (2010): Primary 11Y16, 11Y35; Secondary 11Y11
- DOI: https://doi.org/10.1090/S0025-5718-2014-02837-8
- MathSciNet review: 3266962
Dedicated: Dedicated to Guy Robin on the occasion of his 75th birthday