WorksMathematics
The least Carmichael numbers with prime factors
Abstract
Let denote the least Carmichael number with exactly prime factors. Like the later searches of Pinch, our algorithm builds the prime factors of a candidate in increasing order and stops as soon as the preproduct satisfies . At that point there is at most one possible cofactor, and we recover all of its prime factors at once in polynomial time. We prove an unconditional bound on the number of candidates the search examines, in terms of how far exceeds the product of the first primes. When the search is run in doubling passes, this gives a running time of under a natural conjecture on the size of . We also show that the constant in the exponent is sharp for the set of square-free numbers that the bound counts. Finally, we compute for every ; Pinch had computed it for .
Introduction
Carmichael numbers are the composite numbers satisfying for every integer . Fermat’s little theorem says that the congruence must hold whenever is a prime, and so these numbers might also be called absolute Fermat pseudoprimes. In [3], Robert Carmichael proved that such numbers must be square-free and satisfy for every prime , and he gave examples.1
Theorem 1.1 (Korselt’s Criterion). A composite number is a Carmichael number if and only if is square-free and for all prime divisors of $n.
Every Carmichael number has at least three prime factors, and Alford, Granville, and Pomerance proved that there are infinitely many [16], making rigorous a heuristic construction of Erdős [15]. It is natural to ask for the smallest examples with a prescribed number of prime factors. Let denote the least Carmichael number with exactly prime factors. This is sequence A006931 in the OEIS [18]. The present work extends the known values of and analyzes the cost of the algorithm that finds them.
History
The first few values of fall out of complete tabulations of Carmichael numbers. Šimerka’s list contains . The values and appear in Poulet’s 1938 table of base-2 pseudoprimes up to , where the absolute pseudoprimes are marked [4].2 In 1975, J.D. Swift found all Carmichael numbers up to [5], and this gives . Later tabulations refined Swift’s prime-by-prime approach. The tabulations of Pomerance, Selfridge, and Wagstaff to [6] and of Jaeschke to [7] give and , respectively. Keller’s tabulation to gives [8], and Guthmann later extended the tabulation to [9]. Pinch’s tabulation to [10], together with his later extensions [11, 12], most recently to [14], gives through .
Beyond this point the problem changes character. A complete tabulation up to is out of reach for even moderate ; already has 36 digits. Instead, one searches only for Carmichael numbers with exactly prime factors below some bound , and lowers whenever a new example is found. Pinch used this approach to compute for , proving each value minimal, and maintains a table of the results [14]. This paper is the full account of a project at Butler University that began in 2025. Aidan Johnson and the second author, working as undergraduates, found for with an early version of the algorithm described here, extending Pinch’s list by four entries. Those values were presented as a poster [17] and announced in [20], so that the work in progress would be public. We now describe the algorithm in full, analyze it, and extend the computation to .
1.2. Contributions. Our contributions are as follows. We describe an algorithm for finding that refines the prime-by-prime approach. Rather than appending primes until only one remains to be found, the search stops appending primes as soon as the preproduct satisfies , much as Pinch’s later searches did [11]. The new ingredient is what happens next. All of the remaining prime factors are recovered at once from the single candidate , with , using the polynomial-time algorithm of [20]. We prove an unconditional bound on the number of candidates this algorithm considers, in terms of how far exceeds the product of the first primes. Under a natural conjecture on , this gives a running time of . We show that the constant in the exponent is sharp for the square-free numbers the bound counts, so that any further savings must come from admissibility. We also give a heuristic that makes a prediction we find especially pleasing: if the number of primes recovered by factoring grows sublinearly in , as our data suggest, then the prime-by-prime search and ours agree to leading order, and the advantage of ours is subexponential. Finally, we implemented the algorithm with a work-stealing parallel scheduler and used it to find for .
The remainder of the paper is organized as follows. In § 2, we describe the search tree and the algorithm, and we compare it with the naive and prime-by-prime searches on the same tree. In § 3, we analyze the algorithm as grows. In § 4, we discuss the implementation. In § 5, we give the new values of and statistics on the computation. We conclude in § 6 by comparing with the least cyclic number with prime factors, and by studying the least prime factor of . Along the way we answer a question of Nielsen about the structure of these cyclic numbers.
The Algorithm
Throughout, denotes the th prime, , and is the number of distinct prime factors of . For a squarefree we write for its largest prime factor and
for Carmichael’s function. By Korselt’s criterion, a squarefree with can be a Carmichael number only if , that is,
This requires .
A positive integer is cyclic if . (These are the for which every group of order is cyclic.) A cyclic number is square-free, and for square-free the numbers and have the same prime factors. So the condition above says that is cyclic, and in particular every Carmichael number is cyclic. For a cyclic and a prime , we say that is admissible to if is cyclic, that is, if for every prime . Only admissible primes can be appended to .
The search tree.
Definition 2.1. Fix and . The search tree has root . A node with has as children the nodes , where runs over the primes admissible to in the interval
(with P$ has depth .
The upper endpoint guarantees that can still be completed by larger primes without exceeding . Every cyclic with appears exactly once as a depth- node, through its factors in increasing order.
Three algorithms on one tree.
We compare three ways of searching . They differ only in where they stop enumerating primes explicitly.
N (naive) Explores all of . Every depth- node is a complete candidate and is tested with Korselt’s criterion.
P (prime by prime) Explores depths . At each depth- node it runs through with , and tests for primality.
W (this paper) A node of depth becomes a leaf if or . At a leaf it runs through with . For each such it asks whether is a Carmichael number. Pseudocode is given in Algorithm 1.
The search begins with , where we take for . The heart of the method is the test in line 2. Once it holds, every completion satisfies , so is the only possibility, and testing it directly is cheaper than branching further. (The same observation, that at most Carmichael numbers are divisible by , appears in Pomerance’s account of the upper bound for the number of Carmichael numbers [25 (5.3)].) Some branches never reach , and the test ensures that these end in a leaf too. At every leaf, the loop in lines 5–10 runs over all completions of up to ; when it runs at most once. So the test in line 2 affects only the cost of the search and not its correctness, which gives us freedom in how we implement it (see § 4). Algorithm P is obtained by
Algorithm 1 Carmichael numbers with
Require: The tabulation bound , a preproduct with largest prime , , and the number of primes still to be found.
function Search
if or then
the least with
while do
if is a Carmichael number with prime factors then
report and break
end if
end while
else
for each prime admissible to in do
Search
end for
end if
end function
replacing the test in line 2 with , in which case line 6 only needs to ask whether is prime.
Pinch’s later searches [11, 12] go further than . They stop at a level where is large enough to limit the possible cofactors, and factor those cofactors directly, so they visit essentially the tree of W. The candidate counts of § 3 apply to them as well. Where they differ is line 6. Pinch did not specify a factoring method, and for the purposes of analysis any method can be used, but no general factoring algorithm is known to run in polynomial time. In W the cofactor is not factored in isolation. Line 6 works with itself, and the algorithm of [20] answers it in polynomial time. So for W the bounds of § 3 bound the running time, and not only the number of candidates.
Line 6 is an instance of the decision problem carmichaels: given , is a Carmichael number? This is answered in polynomial time by [20], and we discuss how in § 2.3. If the answer is yes, then is a multiple of , which lets us factor completely, and so counting its prime factors costs nothing extra. Since increases along the progression, the first Carmichael number found at a leaf is the least one there, and there is no reason to continue.
Definition 2.2. At a leaf of depth , the factoring step recovers the remaining primes. Let be the average of over the leaves of W with , in a search with close to .
Algorithm P corresponds to always recovering exactly one prime. The gain of W comes from being larger. § 3 shows , and in our computations grows slowly with (Table 1).
| 20 | 2.924 | 40 | 5.726 | 46 | 5.984 | 54 | 6.562 |
| 24 | 3.486 | 41 | 5.651 | 47 | 6.121 | 55 | 6.655 |
| 29 | 4.145 | 42 | 5.805 | 48 | 6.253 | 56 | 6.752 |
| 34 | 5.015 | 43 | 5.927 | 49 | 6.180 | 59 | 6.968 |
| 36 | 5.460 | 44 | 5.707 | 50 | 6.275 | 60 | 6.990 |
| 39 | 5.396 | 45 | 5.936 | 51 | 6.404 | 63 | 7.211 |
Table 1. The average number of primes recovered by factoring, over all leaves with , measured during clean passes.
The Carmichael query
We answer line 6 with the algorithm of [20], which uses Fermat tests modulo and GCDs to factor . Its correctness is unconditional. It runs in deterministic polynomial time under ERH, and in expected polynomial time unconditionally if the bases are chosen at random [20 Thm. 10]. We describe our implementation of it in § 4.
Analysis of the algorithm
Every node visited by N, P, or W is a node of . The following two constraints on nodes are what drive everything below.
Lemma 3.1. Let be a node of of depth . Then
(i) ;
(ii) .
Proof. (i) with a child of , which has depth , so ; that is, . (ii) Since , we have , so by (i) . □
An unconditional bound
We want to count the nodes of . By Lemma 3.1(ii), a node of depth is a square-free number up to with exactly prime factors. So it is enough to count those numbers, and here we ignore admissibility entirely. The argument has three steps. First, Rankin’s trick (Lemma 3.2) bounds the count by an Euler product , with two free parameters and . Second, we estimate the logarithm of that product. It is a sum over primes, and the primes that matter lie near , where there are about of them per unit of . So the sum is times an integral, up to (Lemma 3.3(b)). Third, we choose and to make the bound as small as possible. What comes out is , where measures how far exceeds the product of the first primes, and is defined by that optimization (Theorem 3.4).
Lemma 3.2 (Rankin’s bound [23]). Let be a set of primes, , , and let be the number of squarefree with and all prime factors in . For every and ,
Proof. Each counted has . The middle sum is at most times the coefficient of in , and since every coefficient is nonnegative, that coefficient is at most times the whole product. □
This is Rankin’s method. Pomerance [25] gives an exposition with many applications, among them an upper bound for the number of Carmichael numbers.
Write
Since is the logarithm of the product of the first primes, measures the excess of the search bound over the smallest conceivable -factor product, per prime. For put
The constant is the integral from the second step, and we evaluate it in the proof of Lemma 3.3(b). The closed form is not needed for the bound itself. But it makes explicit, and its expansion for large is the source of the Hardy–Ramanujan constant in the remark on small excess below. Define, for ,
Lemma 3.3. As :
(a) ;
(b) for fixed , , the sum over all primes, uniformly for .
Proof. (a) By partial summation, . Take and use .
(b) Put , so the sum is . Fix . Primes contribute , since for . Primes contribute at most . On the middle range, by the prime number theorem, so the contribution is . Integrating by parts, , where the last step substitutes and uses the Beta integral with , together with Euler’s reflection formula. Scaling gives . Let . Each error term above is bounded independently of , so the estimate is uniform in .
Theorem 3.4. Fix and suppose . Then, as :
(i) the number of depth- nodes of is at most ;
(ii) ;
(iii) each of N, P, W examines at most candidates (tree nodes plus arithmetic-progression terms), and every prime it enumerates is at most .
Proof. Fix , let , and apply Lemma 3.2 with the set of all primes and .
Depth . By Lemma 3.1(ii) the depth- nodes are counted by , and
By hypothesis and Lemma 3.3(a), . By Lemma 3.3(b), the right-hand side is at most . Choosing (so , since and ; the is uniform in by Lemma 3.3(b)) and using gives
For this is . For general use . Summing over the depths only adds . Since was arbitrary, (i) and (ii) follow.
Progression terms. For P and W, a leaf yields at most $1+B/(P\lambda(P))$ terms (compare [25 (5.3)]). If this is at most 2, and those leaves are already counted in (ii). Otherwise has depth . Then $\lambda(P)\ge p_{\max}(P), and by Lemma 3.1(i). So , because . Summing over all squarefree with and applying the middle inequality of Lemma 3.2 gives
Since , this is the case of the bound above up to .
Largest prime. A child of a depth- node satisfies . Hence , so .
Remark 3.5. Taking in Lemma 3.2 recovers, up to a factor , the binomial count of -subsets of a finite set of primes . That count ignores the constraint , which is what actually limits the search. This is why the proof of Theorem 3.4 uses a constant .
Remark 3.6. Theorem 3.4 uses neither admissibility nor any information about beyond the trivial . It holds for any search of this shape. Admissibility and the actual size of can only improve the constants.
Finding without knowing it
Theorem 3.4 bounds the cost of searching for any . It does not assume that . A search with simply finds nothing, and a search with finds . To find we must therefore choose , and we do not know in advance. One might worry that the analysis is circular: we use a heuristic to choose , and then analyze the search with that . It is not, because the procedure we actually run does not need to know .
Definition 3.7 (Doubling passes). Let be the product of the first odd primes. For , search , and stop at the first pass that finds a Carmichael number with prime factors. Report the least one found in that pass.
Every Carmichael number is odd and square-free, so . Pass finds exactly when , and so the procedure stops at the least such and reports . In particular the final bound satisfies . (The factor 2 is not special; with any constant ratio the final bound satisfies , which changes by only .) If no Carmichael number with prime factors exists, then the procedure does not stop. This is not a concern in our range: Alford, Grantham, Hayman, and Shallue constructed Carmichael numbers with exactly prime factors for every [13].
The cost of the procedure is governed by how far lies above the product of the first primes. Define by
so that is the quantity of (1) evaluated at . This is a property of the sequence alone, and it involves no choice on our part.
Corollary 3.8. Let , and suppose . Then running any of N, P, W in doubling passes finds after examining at most
candidates in total. Since , the running time is
Here the per-candidate cost is that of a Korselt check for , a deterministic primality test for (unconditionally polynomial, by [21]), and the factoring step of [20] for . For this bound is unconditional for the expected running time of the randomized factoring step; see § 2.3.
Proof. Fix . For all large we have . Every pass has , so
for large . By Theorem 3.4(iii), each pass examines at most candidates. The number of passes is at most . Since , this is at most . The factor is absorbed into the in the exponent. Finally, is continuous, so we may let . The per-candidate cost is polynomial in , which is .
The bound in Corollary 3.8 is output-sensitive. It is stated in terms of the answer , through , but the procedure itself uses no information about . The only hypothesis is that is finite, which is a statement about the size of and not about the algorithm. The bound also covers the table of primes the search needs. By the proof of Theorem 3.4, no node contains a prime larger than , and a table of the primes up to that size costs . Since , this does not change the exponent.
In practice we start at a bound given by a heuristic formula, rather than at the product of the first odd primes. This changes only which of the cheap early passes are skipped. If the formula undershoots , nothing in the analysis changes. If it overshoots, say , then the single pass costs . So a heuristic that overshoots by a factor of does not change the exponent.
It remains to say why should be finite. For , let be the least number such that the interval contains primes, and let be the product of those primes.
Conjecture 3.9. for all .
Proposition 3.10. . Consequently, Conjecture 3.9 implies , and so .
Proof. By the prime number theorem , so this satisfies . Every factor of is at most , so . Compare with .
The sharp constant
Theorem 3.4 is only an upper bound, and Rankin’s method can be generous. Here we show that it is not, for the set the theorem counts: is the true constant for the square-free numbers with prime factors. So the gap between the theorem and our data (§ 3.7) comes from admissibility, which the theorem ignores, and not from Rankin’s method.
The optimal and in the proof of Theorem 3.4 form a saddle point. For smooth numbers [27] and for integers with a given number of prime factors [26] (see also [28]), the saddle-point method shows that an optimized Rankin bound has the correct exponential order. Our regime lies beyond the range of those results: formula of [26] for holds for , while we need . But at exponential scale a direct construction suffices. We choose a fixed fraction of the primes in each of a bounded number of ranges near , and count the choices with binomial coefficients. The fractions come from the optimal parameters in Rankin’s bound. Because the ranges have length proportional to , the prime number theorem is all we need. Erdős and Nicolas [24] used the same kind of construction for the case .
Write for .
Theorem 3.11. Fix , and let be the number of square-free with . Then as .
The upper bound is the case of the proof of Theorem 3.4, which counts all square-free with and never uses admissibility. The lower bound rests on two lemmas.
Lemma 3.12. Fix . The infimum defining is attained at some . Put and for . Then
Proof. Let . As we have , and since , so at both ends of . It is continuous, so its infimum is attained at some .
For and put , so that , and put
where the closed form for is the computation in the proof of Lemma 3.3(b). For fixed , is a convex function of , minimized where , and there . So , with minimizer , and .
(a) , which is at .
(b) Differentiating under the integral sign (by dominated convergence, for in a compact subset of ), . Since at , we get . At the minimum , which is (b).
(c) Write , so , , and . Then
Integrating and using (a) and (b), . □
The integrals in Lemma 3.12 converge absolutely. Near we have and , and for large we have and , with .
Lemma 3.13. Fix and . For all large there are at least square-free with and .
Proof. Let be as in Lemma 3.12. Choose parameters and , in that order, as described at the end of the proof. Let be the consecutive intervals of length that partition , taking to be an integer, and let be the left endpoint of . Every we build is the product of all primes and, for each , a set of primes with . These primes are distinct, so is square-free. Let be the number of primes with , and let . Since the lie in the fixed range , the prime number theorem and give , uniformly in , and .
Choice of the . Start from . Since is decreasing, differs from by at most , so by Lemma 3.12(a)
So the defect satisfies , where . Let be the set of with , and let . For the block has at least unused primes and at least chosen ones. If , we can absorb by changing each with by at most , in the direction of the sign of . This gives with and , so that every built has , and with for and for .
Counting. The number of such is , and . Let be a modulus of continuity for on . Then
Here the term comes from the blocks in , which contain at most primes in all, and every other block loses only . As , , and by Lemma 3.12(c) this is minus the two tails and .
Size. Since exactly primes divide ,
The first term is by Lemma 3.3(a). For the second, the partial summation in the proof of Lemma 3.3(a), applied at , gives
For the third, each prime counted in has , and there are at most of them. Also for all , and for . So the third term is
and as . By Lemma 3.12(b), , and both tails tend to as and . Putting the three terms together, is times a quantity that tends to as , then , then , plus .
Choice of parameters. Given , choose small and then large, so that and so that , the four tails, and are all small compared with . Then choose small compared with and with . For all large , both the count and the size then satisfy the bounds claimed. □
Proof of Theorem 3.11. It remains to prove the lower bound. The function is an infimum of functions that are affine in , so it is concave, and hence continuous, on . Given , apply Lemma 3.13 with in place of and in place of . Every it produces has , so for all large . Let . □
Remark 3.14 (Small excess). As , we have , the Hardy–Ramanujan constant [29]. That is what one expects if the primes near were evenly spaced, since then the numbers counted in Theorem 3.11 would correspond to partitions of about . Erdős and Nicolas [24 p. 10] use the same partition heuristic.
The number of primes recovered by factoring.
Proposition 3.15. For , every leaf of has fewer than primes remaining. In particular .
Proof. Let be a leaf of depth , so that primes remain. If the leaf arose from the rule , then . Otherwise . By Lemma 3.1(i), and since gives ,
Hence , that is, . □
Table 1 shows as measured in our computations. It grows slowly with , from about 3 at to about 7 at , and stays far below the bound of Proposition 3.15. Algorithm P recovers exactly one prime per leaf. For our largest and most expensive searches, W recovers on average six to seven times as many. We have no proof that keeps growing.
The bound in each run was close to, but not exactly, , and the runs for different used different versions of our code. This may account for the small departures from monotonicity (for example at and ).
Where N, P, and W differ.
One might expect the three algorithms to differ the way , , and do, where are the numbers of primes each must have available. An implementation with a fixed table of primes invites this picture. But it ignores the constraint (Remark 3.5), which the search enforces at every node through the bound in line 12, and without that constraint the three counts would differ exponentially. With it, we do not think they do. Theorem 3.4 gives the same upper bound for all three algorithms, and we expect them to share the leading constant as well (Heuristic 3.16). The proof of Theorem 3.11 suggests why. The count behaves like a product of binomial coefficients over ranges of primes near . The smallest primes are nearly forced, and almost all of the freedom lies in the primes near . The three algorithms differ only in how many of the last choices they leave to a test instead of enumerating: none for N, one for P, and for W.
Algorithm P removes only the largest prime from explicit enumeration. Algorithm W removes the largest primes. By Proposition 3.15, . Over our range grows, but falls slowly, from about 0.15 for to 0.11 at (Table 1). This is consistent with , but the range is too short to establish it.
Let , , and be the numbers of candidates that the three algorithms examine in a search with close to .
Heuristic 3.16. If , then , , and agree up to , and all are at most , where is defined by . The advantage of W over N comes from the choices of the largest primes, which contribute to the count.
Heuristic 3.16 contains a second assumption, which we make explicit. Most of the cost of P lies in interior nodes, and Theorem 3.4 bounds those only by . The heuristic assumes that, at exponential scale, interior nodes are no more numerous than leaves. This is plausible, since an interior node of depth fixes only small primes, which contribute little to the count, and leaves the primes near unchosen, but we have not proved it.
In short, we expect the three algorithms to be equivalent at exponential scale, and the improvement from the W base case to be subexponential, governed by . If could be shown to grow linearly in (which does not exclude), W would improve the leading constant itself. The size of at the leaves controls , through . If we had better heuristics for the size of when is a product of many small admissible primes, we could estimate , and with it the advantage of W, directly. We leave this as an open problem. See [22] for a step in this direction, an upper bound for the number of with .
Admissibility
The tree contains only admissible products. The counts in Theorems 3.4 and 3.11 do not use this, and are over all square-free products. How much smaller is the tree? We do not know in general. Remark 3.17 shows that the upper bounds still hold and that, for , the tree is still exponentially large. Proposition 3.18 shows that a fixed small prime prunes the tree heavily. A product containing it must avoid many other primes, and so it must be larger by a factor exponential in .
Remark 3.17 (Admissibility). We record what admissibility does and does not change.
(a) The upper bounds are unaffected. Admissible products are a subset of all square-free products, so Theorem 3.4 and Corollary 3.8 hold as stated.
(b) Admissibility does not reduce the order of the tree. If are primes in an interval , then , since would force . So any set of primes in such an interval is pairwise admissible, and every product of of them is a depth- node of once it is at most . Fix and take . By the prime number theorem the interval contains primes, and any of them have product at most , where
Hence, for every , choosing with shows that has at least nodes of depth . Together with (a), the tree has size in this range.
(c) We do not know how admissibility affects the constant . The density of primes admissible to depends on which small primes divide , so it is not a uniform thinning of the primes, and Theorem 3.11 is a statement about all square-free products.
Admissibility matters most for the small primes. A prime in makes every prime inadmissible, which is a proportion of all primes. For this is half of them. For the search, this is pruning, and the subtree below is thin. For the products themselves, it means that a product containing must be larger, as the next result shows.
Proposition 3.18 (Small primes force larger products). Let be a fixed finite set of odd primes, and put
As , every depth- node of that is divisible by every prime in satisfies
In particular, if a fixed prime divides , then .
Proof. Let , and let be the set of primes with for every . Let be a prime factor of not in , and let . If , then because is admissible; if , then is impossible. So every prime factor of outside lies in . The set is the set of primes in of the reduced residue classes modulo . By the prime number theorem for arithmetic progressions, it contains primes up to . Hence its -th element satisfies . Since has at least prime factors in ,
and the first three terms are . For the last claim, is a depth- node of . □
So a fixed small prime adds about to . This is for , for , and roughly in general. Including saves only the ratio of to the prime it displaces, which is . The proposition alone does not exclude any prime from in our range, since there and . But it does show that if , then for all large .
Theory and practice
The bounds above are far from what we observe. For the new values, falls from about 0.88 at to about 0.81 at (Table 2). At we have , so Theorem 3.4 allows on the order of nodes of depth . At a given we can also evaluate the bound of Lemma 3.2 directly. For , minimizing it numerically over and gives about at and at . In our clean passes with the same , the number of leaves with was about at and at . That is growth like , and the counts are smaller than the bound by more than thirty orders of magnitude.
| digits | digits | ||||||||
| 40 | 84 | 17 | 1409 | 0.881 | 53 | 118 | 19 | 1297 | 0.838 |
| 41 | 87 | 17 | 769 | 0.891 | 54 | 121 | 19 | 1051 | 0.845 |
| 42 | 89 | 17 | 1153 | 0.879 | 55 | 124 | 19 | 953 | 0.839 |
| 43 | 92 | 17 | 641 | 0.869 | 56 | 126 | 19 | 1009 | 0.832 |
| 44 | 95 | 17 | 859 | 0.892 | 57 | 129 | 19 | 1123 | 0.827 |
| 45 | 97 | 17 | 601 | 0.873 | 58 | 132 | 19 | 1123 | 0.817 |
| 46 | 100 | 17 | 757 | 0.872 | 59 | 134 | 19 | 1321 | 0.817 |
| 47 | 102 | 17 | 691 | 0.860 | 60 | 137 | 19 | 1873 | 0.817 |
| 48 | 105 | 17 | 1009 | 0.849 | 61 | 140 | 19 | 2689 | 0.801 |
| 49 | 108 | 17 | 1289 | 0.864 | 62 | 143 | 19 | 1471 | 0.806 |
| 50 | 110 | 17 | 937 | 0.856 | 63 | 145 | 19 | 1201 | 0.807 |
| 51 | 113 | 19 | 691 | 0.845 | 64 | 148 | 19 | 1579 | 0.807 |
| 52 | 116 | 19 | 1051 | 0.857 |
Table 2. The new values of : the number of decimal digits, the least and greatest prime factors, and , defined by .
The data do support Conjecture 3.9. For every , is smaller than , by a factor of about at , growing to about at .
By Theorem 3.11, Rankin’s method is not what loses here. The bound counts all square-free products, while the tree contains only admissible ones (Remark 3.17(c)). It also counts nodes of depth , while the leaves of lie about levels higher. We have not measured these two effects separately. Proposition 3.18 shows that each small prime in prunes the tree heavily, and contains many small primes. The lower bound of Remark 3.17(b) does not reach our data either, since it needs . So the exponential order is proved only for larger than we observe, and the constant that governs our computations is not explained by the analysis. Modeling admissibility well enough to predict the observed constant is, we think, the main open problem left by this paper. We return to this in § 6. There we measure the effect of admissibility directly, by comparing with the least cyclic number with prime factors, and we look at one visible effect of it, the least prime factor of .
Implementation
Algorithm 1 is short, and our implementation of it is not. In this section we describe the implementation by referring to the lines of Algorithm 1. None of the changes below alter the search tree; they change only how quickly we walk it. Our code is written in C++ and uses GMP for multiprecision arithmetic. It is available at https://github.com/jewebste/small-carmichael-numbers.
The preproduct and (lines 2 and 13)
Most nodes of the tree are interior, so the cost of line 13 is paid far more often than the cost of a leaf. We avoid multiprecision arithmetic there whenever possible. We store as a GMP integer times a 64-bit accumulator. Appending multiplies only the accumulator, and the accumulator is folded into the GMP integer when the product would overflow. The same is done for . We also keep in factored form, as the exponents of 2, 3, 5, and 7 together with a short sorted list of larger prime powers. The point is to keep Euclid’s algorithm out of line 13. Computed directly, needs a gcd at every interior node, and for the larger the number does not fit in a machine word. Instead we precompute the factorization of for every prime in range. Line 13 is then a merge of two short sorted lists, keeping the larger exponent of each prime, and is multiplied only by the prime powers that grow. The merge is faster than Euclid’s algorithm. Together with the additive update of described below, it saved 6 to 11 percent of the total running time for . Often , and then the child shares the parent’s and nothing is copied.
Euclid’s algorithm still appears once per leaf, in line 3, where is computed by a modular inversion. We do not know how to avoid it. Can be computed incrementally from the parent, or amortized over the leaves below a common ancestor? The difficulty is that the modulus changes from to at each step, so the parent’s inverse is an inverse modulo the wrong number. We leave this as an open question.
We do not store the prime factors of . A node carries , in factored form, and the bit vector of admissible primes described below, but no list of the primes in . The search never needs one. Admissibility is tracked by the bit vector, and is updated from the factorization of alone. We need the factorization of only when line 6 accepts it, and that happens a handful of times in a whole search. At that point the query has already split into its primes, and we recover the primes of by dividing by the primes up to .
We perform the test in line 2 with floating-point logarithms. Both and are updated additively in line 13, using a table of . A rounding error here can only move a node to the wrong branch of line 2, which affects the cost but not the correctness (see § 2). The constant 2 in line 2 is a parameter of our code, and 2 is the value we used in practice. For the larger in Table 1, constants as large as 5 could be used with no major change to the behavior of the algorithm. Replacing 2 by affects only nodes that reach or fewer remaining primes while . But almost every leaf with has at least 5 primes remaining; those with 4 or fewer make up less than 1% of the leaves for each that we measured. For small , where is closer to 3, this is no longer true.
Admissible primes as bit masks (line 12)
The loop in line 12 is the innermost loop of the search, and we implement it with bit masks. The integers up to a compile-time bound MAX_PRIME that are coprime to 30 are encoded as bits, eight per block of 30. At start-up we clear the composite bits with a sieve of Eratosthenes, and for each prime we precompute a mask that clears every . Each node carries its own bit vector of primes admissible to . In line 13, the child’s vector is the parent’s vector ANDed with , and only the words above need to be touched. Line 12 then reduces to repeatedly finding the next set bit (a count-trailing-zeros instruction) until the prime exceeds . We compute that bound once per node, with one call to exp, and recompute it only when changes.
Two cautions are in order. First, the encoding omits 3 and 5, so the search does not see Carmichael numbers divisible by 3 or 5. Nothing is lost in our range. Every Carmichael number is cyclic, and a branch-and-bound search like the one for in § 6 shows that, for every , no cyclic number with prime factors that is divisible by 3 or by 5 is less than . For 3 the margin is wide: the least cyclic number with prime factors divisible by 3 exceeds by a factor of more than for . Second, if ever exceeds MAX PRIME, then the search aborts rather than skip primes. We then recompile with a larger bound and resume at the failed subtree.
4.3. The pair step (lines 12 and 13). Near the root, line 12 runs over small primes, and nearly every child is again an interior node. For we skip the intermediate level and append two primes at once. At start-up we tabulate, for each such , the primes admissible to , together with the combined mask and the factorization of . A node then creates its grandchildren directly from this table. This saves the cost of building the intermediate frames. It does not change the leaves or the work done there.
4.4. The leaf (lines 3–10). In line 4 we start the progression higher than . The cofactor is a product of primes, each larger than , so we may start at the least term exceeding . When the search is run in passes with increasing bounds (see Section 4.8), we also start above , where is the bound of the previous pass.
If , then the loop in lines 5–10 runs at most once. Indeed, any completion satisfies and , so . The only candidate is , and it is a candidate only if and ; the next term already has . We check in floating point before forming , and we discard unless .
In every computation reported here, this is the only kind of leaf that mattered. The other branch of line 2, a leaf with and , is there for correctness. We never saw it taken in any meaningful computational regime, and we exercised it only in regimes constructed for testing. For completeness, our code handles it by sieving the progression: for each prime MAX PRIME that is at most or is not admissible to , we mark the terms divisible by , and only the unmarked terms reach line 6.
4.5. The Carmichael query (line 6). We answer line 6 with the Fermat-test and GCD method of [20], restricted to . Write with odd. Since for every by construction, holds automatically. So we need only check , and all of the arithmetic can be done modulo instead of modulo . If and is prime, we reject at once. Otherwise, for we compute , reject if , and split each un-factored divisor of by gcd. We stop when every part is prime, and accept if there are exactly parts , each with .
One might ask “Why not trial divide first?” We tried this, and it does not help. The exponentiations that build confidence that is a Carmichael number (and so warrant spending computational effort on factoring ) produce the factors of as a byproduct. By the time enough bases have passed, has usually factored already. A separate pre-filter either rediscovers those factors or is spent on a candidate that would have failed anyway.
4.6. From recursion to an explicit stack. The recursion in line 13 is not deep (at most levels), so the hardware stack is not a concern. But a recursive call cannot be handed to another thread. We therefore replaced the hardware stack by a software one. A frame holds , , the bit vector of admissible primes, the bound , and the position of the loop in line 12. The main loop pops a frame, advances its loop by one prime, and pushes the child. A frame is then a self-contained description of an unexplored subtree, and that is exactly what a parallel scheduler needs.
4.7. Work stealing. Our first parallel version cut the tree at a fixed depth and dealt the subtrees out round-robin. This failed in the familiar way: a few subtrees rooted at small primes contain most of the work, and most threads sat idle while those few finished.
We now use work stealing [30]. Each thread owns a local stack and a deque. When a thread creates a child frame in line 13, it decides whether the child might be expensive. If the child’s interval in line 12 is wide, in the sense that
for a parameter , the child is pushed onto the thread’s deque; otherwise it stays on the local stack. A thread takes work from the back of its own deque, and an idle thread steals from the front of another’s, so that thieves take the oldest and typically largest subtrees [30, 31]. We protect each deque with a mutex rather than using a lock-free deque, since the deques see little traffic. As far as we know, this interval-width test is our own heuristic, and we do not have a citation for it. We typically used , chosen after a fair amount of experimentation. We did not study the choice of systematically, and we leave it as an under-investigated question.
The bound is shared. Threads read without locking (a stale value is safe, just slightly wasteful), and a thread that finds a Carmichael number lowers under a lock.
A master thread enumerates the first four primes of in order and launches the workers on each resulting subtree. When the workers rejoin, that subtree is finished, which gives us a checkpoint; a restart skips every subtree up to the last checkpoint.
4.8. Passes and clean passes. We do not know in advance, so we run the doubling passes of Definition 3.7, except that the initial bound comes from a heuristic formula (see the discussion after Corollary 3.8). We take , where is the nearest integer to . The constants are an empirical fit and have no theoretical basis; we compare this formula with Pinch’s estimate in Section 5. The program also accepts a starting bound on the command line, in place of the formula. With the lower bound in line 4, the pass with bound examines only the that the previous pass did not. Within a pass, when a Carmichael number is found, we may lower to it. To certify we instead run a clean pass, with fixed for the whole pass. A clean pass is then an exhaustive search of a known range, and its claim is easy to state: no Carmichael number with prime factors up to is smaller than the least one it reports. (The break in line 7 can skip later terms of a progression, but those are larger than the term just reported.) It also makes the pass independent of the order in which threads happen to find things. The tree that is searched depends only on and , so counts such as in Table 1 are well defined and repeatable.
Results
We found for every . Table 2 summarizes the new values, and the complete values are in OEIS A006931 [18]. Multiplying out each factorization and checking Korselt’s criterion shows that each value is a Carmichael number with prime factors. Minimality rests on the computation. For each value we ran a clean pass (Section 4.8) with , and it found no smaller Carmichael number with prime factors. Our code is public, so that anyone can repeat these runs.
Pinch suggested that might be well approximated by , and noted some support for this from the ratios for [12]. Those ratios fall from 1.27 at to 0.984 at , and our values continue the trend, reaching 0.940 at . If is finite, then the ratio tends to , so the two heuristics cannot both be right. The value of falls from 1.23 at to 0.91 at , and to 0.81 at (Table 2), which we take as modest support for the hypothesis of Corollary 3.8. The formula we used for the starting bound (Section 4.8) is a fit to the same data and has no better claim to the limit. It implies that grows, like , but it stays within 3.3 bits of for .
Hardware and running times
We developed and timed the code on a MacBook, using a single core. Table 3 gives the total time to find there, including every doubling pass from the heuristic starting bound.
| time (s) | time (s) | time (s) | |||
| 20 | 0.12 | 26 | 1.2 | 32 | 36.1 |
| 21 | 0.57 | 27 | 9.0 | 33 | 46.9 |
| 22 | 0.36 | 28 | 5.9 | 34 | 48.5 |
| 23 | 0.34 | 29 | 11.5 | 35 | 200.3 |
| 24 | 0.18 | 30 | 13.8 | 37 | 42.6 |
| 25 | 2.0 | 31 | 4.7 | 38 | 760.2 |
| 39 | 2 911.1 | ||||
| 44 | 44 033.6 |
Table 3. Time to find on one core of a MacBook, including all doubling passes.
The times are far from monotone in . Most of the variation comes from where the heuristic starting bound lands relative to , which decides how many passes are needed and how far the last pass overshoots.
The expensive computations, and every value with , were run on nodes with an AMD EPYC 9734 processor (112 cores), using the work-stealing code of § 4 with 112 threads. For most of these runs we did not keep careful timing data, and the values of missing from Table 4 are those for which we have none. Table 4 gives the times we have, each for a single clean pass with a little above .
| time (s) | time (s) | ||||
| 40 | 1.05 | 1 012 | 50 | 1.05 | 5 305 |
| 41 | 1.05 | 1 226 | 51 | 1.05 | 4 511 |
| 42 | 1.05 | 1 284 | 52 | 1.40 | 55 138 |
| 43 | 1.05 | 1 378 | 54 | 1.77 | 80 779 |
| 45 | 1.05 | 1 833 | 55 | 75 297 | |
| 46 | 1.05 | 2 222 | 56 | 30 639 | |
| 47 | 1.05 | 2 219 | 59 | 48 064 | |
| 48 | 1.05 | 2 258 | 60 | 111 646 | |
| 49 | 1.05 | 5 312 | 61 | 000 | |
| 63 | 712 670 |
Table 4. Wall-clock time of one clean pass with bound , on one AMD EPYC 9734 node with 112 threads.
These times, too, are not monotone in , for two reasons. The ratio varies, and the work in a pass grows quickly with . Also, the wall-clock time of a parallel pass depends on how well the work balances, and a single large subtree can dominate.
Least prime factors and cyclic numbers
The least prime factor of changes slowly. It is at least 11 for every , it is 17 for , and it is 19 for $51 \le k \le 64 ({xref}Table 2). By {xref}Proposition 3.18`, a small prime adds about to , while it saves only the ratio of the prime it displaces, near the top of the product, to . The cost grows linearly in and the saving only logarithmically, so each fixed small prime is eventually excluded. A crude balance of the two suggests a least prime factor of order .
To see how much of this is admissibility alone, we compare with , the least cyclic number with prime factors, which ignores the Korselt condition. We computed for every by branch and bound over the same tree as Algorithm 1. That search is easy, for two reasons: taking admissible primes greedily gives a good bound before the search starts, and at a node with primes left, the product of the next primes admissible to is a sharp lower bound for every completion. Our values agree with the terms of OEIS A264907 [19], which are listed for . Table 5 compares with .
| 10 | 5 | 11 | 0.863 | 1.231 | 1.6 |
| 15 | 7 | 11 | 0.845 | 1.079 | 1.5 |
| 20 | 11 | 11 | 0.831 | 1.013 | 1.6 |
| 25 | 11 | 11 | 0.804 | 0.990 | 2.0 |
| 30 | 11 | 11 | 0.788 | 0.948 | 2.1 |
| 35 | 11 | 17 | 0.767 | 0.913 | 2.2 |
| 40 | 11 | 17 | 0.752 | 0.881 | 2.2 |
| 45 | 11 | 17 | 0.749 | 0.873 | 2.4 |
| 50 | 11 | 17 | 0.738 | 0.856 | 2.6 |
| 53 | 11 | 19 | 0.731 | 0.838 | 2.5 |
| 54 | 19 | 19 | 0.727 | 0.845 | 2.8 |
| 55 | 19 | 19 | 0.724 | 0.839 | 2.7 |
| 60 | 19 | 19 | 0.707 | 0.817 | 2.9 |
| 64 | 19 | 19 | 0.696 | 0.807 | 3.1 |
Table 5. The least cyclic number and the least Carmichael number with prime factors. Here is defined by .
Three things stand out. First, is close to : the ratio is at most for . The part of not explained by admissibility, , falls from 0.37 at to 0.11 at . So at , admissibility alone accounts for about 86% of , and the Korselt condition for the rest. Second, the least prime factor of jumps from 11 to 19 at , skipping 13 and 17, and from then on it agrees with the least prime factor of for every . Third, for the least prime factor of is at least that of , and often larger. We do not think the Korselt condition acts on the small primes directly. A leaf has a Korselt completion only by chance, so is the least of the comparatively few admissible products below it that happen to have one. It therefore resembles a typical admissible product of its size more than the extreme one, , and we expect a typical product to contain fewer small primes, since each small prime excludes a residue class from the rest of the product (Proposition 3.18).
Conjecture 6.1. The least prime factor of tends to infinity with , and it is . Moreover, it equals the least prime factor of for all sufficiently large .
We note a by-product. Nielsen asked [19] whether the prime factors of always form a normal sequence of primes, that is, whether is obtained by choosing a first prime and then repeatedly taking the least prime admissible to all those already chosen. They do not. For , the cyclic number
that we found is already smaller, by a factor of 1.04, than the product of the first 31 terms of every normal sequence. This conclusion does not depend on the minimality of our search. The greedy choice from 11 takes 13, and admitting 13 excludes 53, 79, 131, and 157, which turns out to cost more than 13 saves. For every , is not the product of a normal sequence.
Use of AI tools
This paper was prepared with substantial assistance from Claude (Anthropic), a large language model, used through Claude Code. The algorithm of § 2 is due to the authors. The implementation described in § 4 was written by Claude under our direction, mainly with Claude Sonnet 4.6 and Claude Sonnet 5. The analysis of § 3, including the proofs (among them the proof of Theorem 3.11) and Heuristic 3.16, was carried out primarily by Claude Opus 5.5 under our direction, and was checked by the authors. Claude Opus 5.5 also drafted much of the text from our outlines and revisions, and helped locate and verify references. All editorial and stylistic decisions were made by the first author. The authors take full responsibility for the contents of this paper.
Acknowledgements
We thank Andrew Shallue for helpful discussions. We thank Aidan Johnson for his work on the 2025 project and for researching numerical estimators for . Thanks also to Frank Levinson for generous donations to Butler University that helped make this computation possible.
Mathematical Sciences Department, Butler University
Email address: [email protected]
Mathematical Sciences Department, Butler University
References
- [1]A. Korselt, Problème chinois, L’Intermédiaire des Mathématiciens 6 (1899), 142–143.
- [2]V. Šimerka, Zbytky z arithmetické polosoučtnosti, Časopis pro pěstování mathematiky a fysiky 14 (1885), 221–225.
- [3]R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232–238.DOI
- [4]P. Poulet, Tables des nombres composés vérifiant le théorème de Fermat pour le module 2 jusqu’à 100.000.000, Sphinx (Brussels) 8 (1938), 42–45.
- [5]J. D. Swift, Table of Carmichael numbers to 10^9, Math. Comp. 29 (1975), 338–339.DOI
- [6]C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25 · 10^9, Math. Comp. 35 (1980), 1003–1026.
- [7]G. Jaeschke, Carmichael numbers to 10^12, Math. Comp. 55 (1990), 383–389.DOI
- [8]W. Keller, The Carmichael numbers to 10^13, Abstracts Amer. Math. Soc. 9 (1988), 328–329.
- [9]A. Guthmann, On the computation of Carmichael numbers, Tech. Report 218, Universität Kaiserslautern, 1992.
- [10]R. G. E. Pinch, The Carmichael numbers up to 10^15, Math. Comp. 61 (1993), 381–391.
- [11]R. G. E. Pinch, The Carmichael numbers up to 10^17, arXiv:math/0504119 (2005).DOI
- [12]R. G. E. Pinch, The Carmichael numbers up to 10^18, arXiv:math/0604376 (2006).DOI
- [13]W. R. Alford, J. Grantham, S. Hayman, and A. Shallue, Constructing Carmichael numbers through improved subset-product algorithms, Math. Comp. 83 (2014), 899–915.arxiv.org/abs/1203.6664
- [14]R. G. E. Pinch, Tables of Carmichael numbers, http://www.s369624816.websitehome.co.uk/rgep/cartable.html.
- [15]P. Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206.
- [16]W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703–722.DOI
- [17]A. Johnson, S. Webster, and J. Webster, poster, Butler MRC 2025, https://blue.butler.edu/~jwebste/MRC_2025.pdf.
- [18]The On-Line Encyclopedia of Integer Sequences, Sequence A006931, https://oeis.org/A006931.
- [19]The On-Line Encyclopedia of Integer Sequences, Sequence A264907, https://oeis.org/A264907.
- [20]A. Shallue and J. Webster, Algorithms for Carmichael numbers, arXiv:2506.09903 (2025).arxiv.org/abs/2506.09903
- [21]M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Ann. of Math. 160 (2004), 781–793.DOI
- [22]R. Pollack, Small values of Carmichael’s lambda function, arXiv:2606.19132 (2026).arxiv.org/abs/2606.19132
- [23]R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13 (1938), 242–247.DOI
- [24]P. Erdős and J.-L. Nicolas, Sur la fonction “nombre de facteurs premiers de n”, Enseign. Math. (2) 27 (1981), 3–27.DOI
- [25]C. Pomerance, Two methods in elementary analytic number theory, in R. A. Mollin (ed.), Number Theory and Applications, Kluwer, Dordrecht, 1989, 135–161.
- [26]A. Hildebrand and G. Tenenbaum, On the number of prime factors of an integer, Duke Math. J. 56 (1988), 471–501.DOI
- [27]A. Hildebrand and G. Tenenbaum, On integers free of large prime factors, Trans. Amer. Math. Soc. 296 (1986), 265–290.DOI
- [28]G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, 3rd ed., Graduate Studies in Mathematics 163, Amer. Math. Soc., 2015.DOI
- [29]G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. (2) 17 (1918), 75–115.
- [30]R. D. Blumofe and C. E. Leiserson, Scheduling multithreaded computations by work stealing, J. ACM 46 (1999), 720–748.
- [31]D. Chase and Y. Lev, Dynamic circular work-stealing deque, Proc. SPAA 2005, 21–28.DOI