Update on Algorithms for Carmichael numbers

Andrew Shallue, Jonathan Webster · 2025

Read Update on Algorithms for Carmichael numbers by Andrew Shallue, Jonathan Webster (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-09903.txt.

Introduction

Andrew Shallue and Jonathan Webster report faster ways to hunt Carmichael numbers, the rare composite numbers that pass a famous primality test as if they were prime. Listing all of them below a bound is a classic computing problem whose best method had barely improved in 50 years. The pair first shows the listing task sits in the class P, assuming a standard unproven guess about primes.

They then give a tabulation method that should be close to optimal, the first real asymptotic gain since the prime-by-prime approach appeared. A related program they ran pushed the census 100 times further on about five times the past effort. It found over 308 million Carmichael numbers below ten to the twenty-fourth power.

Catalog record

CREATORAndrew Shallue, Jonathan Webster
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-09903

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Update on Algorithms for Carmichael numbers Andrew Shallue, Jonathan Webster Abstract . In this note, we present progress on determining the computational complexity of tabulating all Carmichael numbers less than some bound B B . We implemented a new tabulation algorithm which we describe here. In lieu of providing an asymptotic analysis of that algorithm, we show a second related algorithm that we claim is optimal under two believable conjectures. 1. Introduction In 1993, R.G.E. Pinch described an algorithm used to find all Carmichael numbers up to 10^{15} [ 4 ] . Over the next 14 years, he used the same algorithm to produce successively larger tabulations ending with 10^{21} [ 5 , 6 , 7 , 8 ] . We revisited this problem and tried to improve Pinch’s approach. In [ 11 ] , we found an asymptotic improvement to the small case. In [ 12 ] , we gave an asymptotic improvement to the large case and showed that the count of inputs to the algorithm was bounded by B\exp\left(\left(-\frac{1}{\sqrt{2}}+o(1)\right)\sqrt{\log B\log\log B}\right). It was believable that the time used per input was polynomial in \log B ; so, the above bound was also a heuristic run time for the algorithm. Timing information demonstrated that our improvement was not very effective (see the final table in [ 12 ] ). We concluded by sharing our suspicion that it should be possible to tabulate Carmichael numbers by “consider[ing] fewer preproducts.” The bound above matches Knödel’s initial bound on the count of Carmichael numbers [ 3 ] . Erdős improved Knödel’s bound on the count [ 2 ] , showing B\exp\left(\frac{-k\log B\log\log\log B}{\log\log B}\right) for some positive constant k . In [ 10 ] , it is shown that k can be chosen to be (1-\epsilon) for any \epsilon>0 . In the same paper, a heuristic argument (combined with a more precise result from analytic number theory, see [ 9 ] ) shows that this is also the lower bound for the count of Carmichael numbers. We follow the argument in [ 10 ] and state a theoretical tabulation algorithm. Precisely, we prove the following theorem conditioned on a believable conjecture. The conjecture is not needed for the correctness of the algorithm. Theorem 1 . For each \epsilon>0 , there is an B_{0}(\epsilon) such that for all B>B_{0}(\epsilon) , there is an algorithm that can find all Carmichael numbers less than B in time B\cdot L(B)^{-1+o(1)} , where L(x)=\exp(\log x\cdot\log_{3}x/\log_{2}x) . The first conjecture we require is that the query “Is n a Carmichael number?” can be answered in polynomial time; see Section 5 for a precise statement of the required conjecture. The second conjecture is only needed for the claim that this algorithm is optimal. If B\cdot L(B)^{-1+o(1)} is the correct asymptotic count of Carmichael numbers, then the algorithm is optimal. To have an asymptotically faster algorithm would immediately improve the current best upper bound on the count of Carmichael numbers and would explain the error in the heuristic argument for the lower bound. Such a result would be of deeper theoretical import than the algorithm itself. In what follows, we set up the required preliminary results from number theory and on Carmichael numbers. We provide a brief review of Pinch’s approach in order to provide context for the improvements offered here. We give a brief example to demonstrate our belief that there were “too many preproducts,” which is also grounded in the different asymptotic counts of Knödel and Erdős. The example poses two algorithmic problems and we address each of those solutions in the next two sections. We state the algorithm we are currently running. In penultimate section, we state and prove the algorithmic realization of the counting argument found in [ 10 ] . Lastly, we conclude with a high-level conceptual overview of the three different algorithmic approaches presented in this note. It might be asked why our implementation differs from the optimal algorithm. We embarked on this work having already completed the “small” case of Pinch’s tabulation regime. As you will see, our new way of dealing with the “large” case bears a striking similarity to the optimal algorithm and the majority of Carmichael numbers are found in the exact same way. Indeed, the existence of our implementation is what allowed us to realize that the optimal recursive algorithm existed. 2. Background 2.1. Number theoretic functions and definitions (1) Let \omega(n) count the distinct prime factors of n . That is, \omega(n)=\sum_{p\mid n}1. (2) Let \lambda(n) be the Carmichael lambda function. Formally, we have \displaystyle\lambda(2^{r}) \displaystyle=2^{r-2} \displaystyle\lambda(p^{r}) \displaystyle=p^{r-1}(p-1) \displaystyle\lambda(n) \displaystyle={\rm lcm}(\lambda(p_{1}^{r_{1}}),\lambda(p_{2}^{r_{2}}),\dots,\lambda(p_{k}^{r_{k}})) where the lcm is taken over the distinct prime powers dividing n . Equivalently, \lambda(n) is the universal exponent of (\mathbb{Z}/n\mathbb{Z})^{\times} . 2.2. Theorems for Carmichael numbers A positive integer n is Carmichael if it is composite and a^{n}\equiv a\mod{n} for all a\in\mathbb{Z}/n\mathbb{Z} . Thus a Carmichael number has the pleasing property that every integer a either shares a factor with n or is a Fermat liar for n . However, we typically take Korselt’s criterion as our working definition for tabulation. Theorem 2 (Korselt’s Criterion) . A composite number n is a Carmichael number if and only if n is squarefree and (p-1)\mid(n-1) for all prime divisors p of n . Equivalently, n is Carmichael iff \lambda(n)\mid(n-1) . Tabulation algorithms construct n in factored form. Let P_{k}=\prod_{i=1}^{k}p_{i} where p_{i}<p_{j} iff i<j . We drop the subscript k from P_{k} when the context does not require a specific count of primes dividing a preproduct. Henceforth, we reserve p to be the greatest prime factor of P . When other letters are used for primes we typically use q or r . Theorem 3 (Proposition 2 of [ 4 ] ) . Let n=Pqr be Carmichael. Then there are integers 2\leq D<P<C such that, putting \Delta=CD-P^{2} , we have q=\frac{(P-1)(P+D)}{\Delta}+1,\quad r=\frac{(P-1)(P+C)}{\Delta}+1,\quad P^{2}<CD<P^{2}\left(\frac{p+3}{p+1}\right). Theorem 4 (Proposition 1 of [ 4 ] ) . Let n be a Carmichael number less than B with d prime factors. (1) Let k<d . Then p_{k+1}<(B/P_{k})^{1/(d-k)} and p_{k+1}-1 is relatively prime to p_{i} for all i\leq k . (2) P_{d-1}r\equiv 1\pmod{\lambda(P_{d-1})} and r-1 divides P_{d-1}-1 . (3) Each p_{i} satisfies p_{i}<\sqrt{n}<\sqrt{B} . The condition that p_{k+1}-1 is relatively prime to p_{i} for all i\leq k means that every P is a cyclic number (in the group theoretic sense). When p_{k+1} satisfies this condition we call the prime admissible with respect to P_{k} . Part 2 of Theorem 4 can be generalized: we have PR\equiv 1\pmod{\lambda(P)} for arbitrary positive R whenever n is Carmichael and n=PR . Enabling composite completions will give needed flexibility in the constructions to follow. The quantity P^{-1}\pmod{\lambda(P)} is used frequently throughout and we let r^{\star} denote the least positive residue in that congruence class. This might be considered an unconventional naming choice but it is due to the fact that we associate this quantity with R , the remaining factor to be constructed. 3. Prior Algorithms We encourage the reader to consult [ 4 , 11 , 12 ] for a thorough explanation. 3.1. Tabulate all Pqr with P<X using Theorem 3 . Create a loop on D in the interval [2,P) . Use an incremental sieve to

Read the complete text