Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

Estimating the counts of Carmichael and Williams numbers with small multiple seeds


Author: Zhenxiang Zhang
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
Published electronically: April 8, 2014
MathSciNet review: 3266962
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \vert\mathcal {C}(L)\vert$ and $ \vert\mathcal {W}(L)\vert$ 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\vert\mathcal {C}(L)\vert=2^{s(1+o(1))}$ and $ \log _2\vert\mathcal {W}(L)\vert=2^{s^{1/2-o(1)}}$ when such an ``even-divisor optimal'' integer $ L$ has $ s$ different prime factors. For example, we determine that $ \vert\mathcal {C}(735134400)\vert > 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 [Enhancements On Off] (What's this?)

  • [1] L. Alaoglu and P. Erdös, On highly composite and similar numbers, Trans. Amer. Math. Soc. 56 (1944), 448-469. MR 0011087 (6,117c)
  • [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 (95k:11114), https://doi.org/10.2307/2118576
  • [3] 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 (2011d:11006), https://doi.org/10.1142/S1793042110002922
  • [4] 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 0384673 (52 #5546)
  • [5] R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), no. 5, 232-238. MR 1558896, https://doi.org/10.1090/S0002-9904-1910-01892-9
  • [6] Zhuo Chen and John Greene, Some comments on Baillie-PSW pseudoprimes, Fibonacci Quart. 41 (2003), no. 4, 334-344. MR 2022413 (2004k:11011)
  • [7] Richard Crandall and Carl Pomerance, Prime numbers: A computational perspective, 2nd ed., Springer, New York, 2005. MR 2156291 (2006a:11005)
  • [8] 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 (99d:11133), https://doi.org/10.1090/S0025-5718-99-01037-6
  • [9] 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 (2009h:11197)
  • [10] P. Erdös, On highly composite numbers, J. London Math. Soc. 19 (1944), 130-133. MR 0013381 (7,145d)
  • [11] P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. MR 0079031 (18,18e)
  • [12] A. Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society 39 (1992), 696-700.
  • [13] A. Korselt, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-143.
  • [14] Jean-Louis Nicolas, Répartition des nombres hautement composés de Ramanujan, Canad. J. Math. 23 (1971), 116-130. MR 0274400 (43 #165)
  • [15] 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.
  • [16] 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
  • [17] 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 (86j:11009)
  • [18] Kenneth H. Rosen, Elementary number theory and its applications, 4th ed., Addison-Wesley, Reading, MA, 2000. MR 1739433 (2000i:11001)
  • [19] H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133-143. MR 0447099 (56 #5414)
  • [20] 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 (2003f:11191), https://doi.org/10.1090/S0025-5718-02-01424-2
  • [21] Zhenxiang Zhang, Counting Carmichael numbers with small seeds, Math. Comp. 80 (2011), no. 273, 437-442. MR 2728989 (2011i:11176), https://doi.org/10.1090/S0025-5718-2010-02382-8

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
Email: ahnu{\textunderscore}zzx@sina.com, ahnu{\textunderscore}zzx@sohu.com

DOI: https://doi.org/10.1090/S0025-5718-2014-02837-8
Keywords: Carmichael numbers (with small multiple seeds), Korselt's criterion, Erd\H{o}s's construction of Carmichael numbers, even-divisors-optimal numbers (EDONs), Williams numbers, algorithms
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.
Dedicated: Dedicated to Guy Robin on the occasion of his 75th birthday
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society