×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alaoglu, L.; Erd{\"o}s, P., On highly composite and similar numbers, Trans. Amer. Math. Soc., 56, 448-469 (1944) · Zbl 0061.07903
[2] 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
[3] 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
[4] 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
[5] Carmichael, R. D., Note on a new number theory function, Bull. Amer. Math. Soc., 16, 5, 232-238 (1910) · JFM 41.0226.04
[6] Chen, Zhuo; Greene, John, Some comments on Baillie-PSW pseudoprimes, Fibonacci Quart., 41, 4, 334-344 (2003) · Zbl 1052.11006
[7] Crandall, Richard; Pomerance, Carl, Prime numbers, xvi+597 pp. (2005), Springer: New York:Springer · Zbl 1088.11001
[8] 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
[9] Echi, Othman, Williams numbers, C. R. Math. Acad. Sci. Soc. R. Can., 29, 2, 41-47 (2007) · Zbl 1204.11185
[10] Erd{\"o}s, P., On highly composite numbers, J. London Math. Soc., 19, 130-133 (1944) · Zbl 0061.07904
[11] Erd{\"o}s, P., On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen, 4, 201-206 (1956) · Zbl 0074.27105
[12] [Gran1992] A. Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society 39 (1992), 696-700.
[13] [Kor] A. Korselt, Probl\`“eme chinois, L”interm\'ediaire des math\'ematiciens 6 (1899), 142-143.
[14] Nicolas, Jean-Louis, R\'epartition des nombres hautement compos\'es de Ramanujan, Canad. J. Math., 23, 116-130 (1971) · Zbl 0213.06602
[15] [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.
[16] 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
[17] 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
[18] Rosen, Kenneth H., Elementary number theory and its applications, xviii+638 pp. (2000), Addison-Wesley: Reading, MA:Addison-Wesley · Zbl 0964.11002
[19] Williams, H. C., On numbers analogous to the Carmichael numbers, Canad. Math. Bull., 20, 1, 133-143 (1977) · Zbl 0368.10011
[20] 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
[21] 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.