# zbMATH — the first resource for mathematics

Estimating the counts of Carmichael and Williams numbers with small multiple seeds. (English) Zbl 1315.11101
Summary: 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.
##### MSC:
 11Y16 Number-theoretic algorithms; complexity 11A51 Factorization; primality 11Y11 Primality
Full Text:
##### References:
  Alaoglu, L.; Erd{\"o}s, P., On highly composite and similar numbers, Trans. Amer. Math. Soc., 56, 448-469 (1944) · Zbl 0061.07903  Alford, W. R.; Granville, Andrew; Pomerance, Carl, There are infinitely many Carmichael numbers, Ann. of Math. (2), 139, 3, 703-722 (1994) · Zbl 0816.11005  Bouall{\e}gue, Kais; Echi, Othman; Pinch, Richard G. E., Korselt numbers and sets, Int. J. Number Theory, 6, 2, 257-269 (2010) · Zbl 1214.11013  Brillhart, John; Lehmer, D. H.; Selfridge, J. L., New primality criteria and factorizations of $$2^m\pm 1$$, Math. Comp., 29, 620-647 (1975) · Zbl 0311.10009  Carmichael, R. D., Note on a new number theory function, Bull. Amer. Math. Soc., 16, 5, 232-238 (1910) · JFM 41.0226.04  Chen, Zhuo; Greene, John, Some comments on Baillie-PSW pseudoprimes, Fibonacci Quart., 41, 4, 334-344 (2003) · Zbl 1052.11006  Crandall, Richard; Pomerance, Carl, Prime numbers, xvi+597 pp. (2005), Springer: New York:Springer · Zbl 1088.11001  Dusart, Pierre, The $$k$$ th prime is greater than $$k(\ln k+\ln \ln k-1)$$ for $$k\geq 2$$, Math. Comp., 68, 225, 411-415 (1999) · Zbl 0913.11039  Echi, Othman, Williams numbers, C. R. Math. Acad. Sci. Soc. R. Can., 29, 2, 41-47 (2007) · Zbl 1204.11185  Erd{\"o}s, P., On highly composite numbers, J. London Math. Soc., 19, 130-133 (1944) · Zbl 0061.07904  Erd{\"o}s, P., On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen, 4, 201-206 (1956) · Zbl 0074.27105  [Gran1992] A. Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society 39 (1992), 696-700.  [Kor] A. Korselt, Probl\“eme chinois, L”interm\'ediaire des math\'ematiciens 6 (1899), 142-143.  Nicolas, Jean-Louis, R\'epartition des nombres hautement compos\'es de Ramanujan, Canad. J. Math., 23, 116-130 (1971) · Zbl 0213.06602  [Pom84] 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.  Ramanujan, S., Highly composite numbers [Proc. London Math. Soc. (2) {\bf 14} (1915), 347-409]. Collected papers of Srinivasa Ramanujan, 78-128 (2000), AMS Chelsea Publ., Providence, RI  Robin, G., M\'ethodes d’optimisation pour un probl\`“eme de th\'”eorie des nombres, RAIRO Inform. Th\'eor., 17, 3, 239-247 (1983) · Zbl 0531.10012  Rosen, Kenneth H., Elementary number theory and its applications, xviii+638 pp. (2000), Addison-Wesley: Reading, MA:Addison-Wesley · Zbl 0964.11002  Williams, H. C., On numbers analogous to the Carmichael numbers, Canad. Math. Bull., 20, 1, 133-143 (1977) · Zbl 0368.10011  Zhang, Zhenxiang, A one-parameter quadratic-base version of the Baillie-PSW probable prime test, Math. Comp., 71, 240, 1699-1734 (2002) · Zbl 1076.11063  Zhang, Zhenxiang, Counting Carmichael numbers with small seeds, Math. Comp., 80, 273, 437-442 (2011) · Zbl 1225.11161
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.