betaFeedback

WorksMathematics

The least Carmichael numbers with kk prime factors

Abstract

Let SkS_k denote the least Carmichael number with exactly kk 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 PP satisfies Pλ(P)>BPλ(P) > B. 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 BB exceeds the product of the first kk primes. When the search is run in doubling passes, this gives a running time of eO(k)=SkO(1/log⁡k)e^{O(k)} = S_k^{O(1/\log k)} under a natural conjecture on the size of SkS_k. 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 SkS_k for every k≤64k \leq 64; Pinch had computed it for k≤35k \leq 35.

Introduction

Carmichael numbers are the composite numbers nn satisfying bn≡b(modn)b^n\equiv b\pmod n for every integer bb. Fermat’s little theorem says that the congruence must hold whenever nn 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 (p−1)∣(n−1)(p-1)\mid(n-1) for every prime p∣np\mid n, and he gave examples.1

Theorem 1.1 (Korselt’s Criterion). A composite number nn is a Carmichael number if and only if nn is square-free and (p−1)∣(n−1)(p-1)\mid(n-1) for all prime divisors pp 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 SkS_k denote the least Carmichael number with exactly kk prime factors. This is sequence A006931 in the OEIS [18]. The present work extends the known values of SkS_k and analyzes the cost of the algorithm that finds them.

History

The first few values of SkS_k fall out of complete tabulations of Carmichael numbers. Šimerka’s list contains S3=561S_3=561. The values S4=41041S_4=41041 and S5=825265S_5=825265 appear in Poulet’s 1938 table of base-2 pseudoprimes up to 10810^8, where the absolute pseudoprimes are marked [4].2 In 1975, J.D. Swift found all Carmichael numbers up to 10910^{9} [5], and this gives S6=321197185S_6 = 321197185. Later tabulations refined Swift’s prime-by-prime approach. The tabulations of Pomerance, Selfridge, and Wagstaff to 25⋅10925 \cdot10^{9} [6] and of Jaeschke to 101210^{12} [7] give S7S_7 and S8S_8, respectively. Keller’s tabulation to 101310^{13} gives S9S_9 [8], and Guthmann later extended the tabulation to 101410^{14} [9]. Pinch’s tabulation to 101510^{15} [10], together with his later extensions [11, 12], most recently to 102110^{21} [14], gives S10S_{10} through S12S_{12}.

Beyond this point the problem changes character. A complete tabulation up to SkS_k is out of reach for even moderate kk; S20S_{20} already has 36 digits. Instead, one searches only for Carmichael numbers with exactly kk prime factors below some bound BB, and lowers BB whenever a new example is found. Pinch used this approach to compute SkS_k for k≤35k \le35, 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 SkS_k for 36≤k≤3936 \le k \le39 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 k=64k = 64.

1.2. Contributions. Our contributions are as follows. We describe an algorithm for finding SkS_k 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 PP satisfies Pλ(P)>BP\lambda(P) > B, 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 n=PRn = PR, with R≡P−1(modλ(P))R \equiv P^{-1} \pmod{\lambda(P)}, 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 BB exceeds the product of the first kk primes. Under a natural conjecture on SkS_k, this gives a running time of eO(k)=SkO(1/log⁡k)e^{O(k)} = S_k^{O(1/\log k)}. 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 kk, 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 SkS_k for 40≤k≤6440 \le k \le64.

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 kk grows. In § 4, we discuss the implementation. In § 5, we give the new values of SkS_k and statistics on the computation. We conclude in § 6 by comparing SkS_k with the least cyclic number with kk prime factors, and by studying the least prime factor of SkS_k. Along the way we answer a question of Nielsen about the structure of these cyclic numbers.

The Algorithm

Throughout, pip_i denotes the iith prime, θ(x)=∑p≤xlog⁡p\theta(x) = \sum_{p \le x} \log p, and ω(n)\omega(n) is the number of distinct prime factors of nn. For a squarefree P>1P > 1 we write pmax⁡(P)p_{\max}(P) for its largest prime factor and

λ(P)=lcm⁡{p−1:p∣P}\lambda(P)=\operatorname{lcm}\{p-1:p\mid P\}

for Carmichael’s function. By Korselt’s criterion, a squarefree n=PRn=PR with gcd⁡(P,R)=1\gcd(P,R)=1 can be a Carmichael number only if λ(P)∣n−1\lambda(P)\mid n-1, that is,

R≡P−1(modλ(P)).R\equiv P^{-1}\pmod{\lambda(P)}.

This requires gcd⁡(P,λ(P))=1\gcd(P,\lambda(P))=1.

A positive integer nn is cyclic if gcd⁡(n,φ(n))=1\gcd(n,\varphi(n))=1. (These are the nn for which every group of order nn is cyclic.) A cyclic number is square-free, and for square-free PP the numbers λ(P)\lambda(P) and φ(P)\varphi(P) have the same prime factors. So the condition above says that PP is cyclic, and in particular every Carmichael number is cyclic. For a cyclic PP and a prime q>pmax⁡(P)q>p_{\max}(P), we say that qq is admissible to PP if PqPq is cyclic, that is, if q≢1(modp)q\not\equiv1\pmod p for every prime p∣Pp\mid P. Only admissible primes can be appended to PP.

The search tree.

Definition 2.1. Fix BB and kk. The search tree T(B,k)\mathcal{T}(B,k) has root P=1P=1. A node PP with ω(P)=j<k\omega(P)=j<k has as children the nodes PqPq, where qq runs over the primes admissible to PP in the interval

pmax⁡(P)<q≤(B/P)1/(k−j)p_{\max}(P)<q\leq(B/P)^{1/(k-j)}

(with pmax⁡(1):=2).Wesayp_{\max}(1):=2). We sayP$ has depth j=ω(P)j=\omega(P).

The upper endpoint guarantees that PP can still be completed by k−jk-j larger primes without exceeding BB. Every cyclic n≤Bn\leq B with ω(n)=k\omega(n)=k appears exactly once as a depth-kk node, through its factors in increasing order.

Three algorithms on one tree.

We compare three ways of searching T(B,k)\mathcal{T}(B,k). They differ only in where they stop enumerating primes explicitly.

N (naive) Explores all of T(B,k)\mathcal{T}(B,k). Every depth-kk node is a complete candidate and is tested with Korselt’s criterion.

P (prime by prime) Explores depths ≤k−1\leq k-1. At each depth-(k−1)(k-1) node PP it runs through R≡P−1(modλ(P))R\equiv P^{-1}\pmod{\lambda(P)} with pmax⁡(P)<R≤B/Pp_{\max}(P)<R\leq B/P, and tests RR for primality.

W (this paper) A node PP of depth jj becomes a leaf if k−j≤2k-j\leq2 or Pλ(P)>BP\lambda(P)>B. At a leaf it runs through R≡P−1(modλ(P))R\equiv P^{-1}\pmod{\lambda(P)} with pmax⁡(P)<R≤B/Pp_{\max}(P)<R\leq B/P. For each such RR it asks whether PRPR is a Carmichael number. Pseudocode is given in Algorithm 1.

The search begins with Search⁡(B,1,1,k)\operatorname{Search}(B,1,1,k), where we take p=2p=2 for P=1P=1. The heart of the method is the test Pλ(P)>BP\lambda(P)>B in line 2. Once it holds, every completion satisfies R≤B/P<λ(P)R\leq B/P<\lambda(P), so R=r∗R=r^{*} is the only possibility, and testing it directly is cheaper than branching further. (The same observation, that at most 1+x/(dλ(d))1+x/(d\lambda(d)) Carmichael numbers n≤xn\leq x are divisible by dd, appears in Pomerance’s account of the upper bound for the number of Carmichael numbers [25 (5.3)].) Some branches never reach Pλ(P)>BP\lambda(P)>B, and the test m≤2m\leq2 ensures that these end in a leaf too. At every leaf, the loop in lines 5–10 runs over all completions of PP up to BB; when Pλ(P)>BP\lambda(P)>B 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 n≤Bn \le B with ω(n)=k\omega(n)=k

Require: The tabulation bound BB, a preproduct PP with largest prime pp, λ(P)\lambda(P), and the number mm of primes still to be found.

  1. function Search(B,P,λ(P),m)(B,P,\lambda(P),m)

  2. &nbsp;&nbsp;if m≤2m \le2 or Pλ(P)>BP\lambda(P)>B then

  3. &nbsp;&nbsp;&nbsp;&nbsp;r⋆←P−1 mod λ(P)r^{\star} \gets P^{-1} \bmod\lambda(P)

  4. &nbsp;&nbsp;&nbsp;&nbsp;R←R \gets the least R≡r⋆(modλ(P))R \equiv r^{\star} \pmod{\lambda(P)} with R>pR>p

  5. &nbsp;&nbsp;&nbsp;&nbsp;while PR≤BPR \le B do

  6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if PRPR is a Carmichael number with kk prime factors then

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;report PRPR and break

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;R←R+λ(P)R \gets R+\lambda(P)

  10. &nbsp;&nbsp;&nbsp;&nbsp;end while

  11. &nbsp;&nbsp;else

  12. &nbsp;&nbsp;&nbsp;&nbsp;for each prime qq admissible to PP in (p,B/Pm]\left(p,\sqrt[m]{B/P}\right] do

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Search(B,Pq,lcm⁡(λ(P),q−1),m−1)(B,Pq,\operatorname{lcm}(\lambda(P),q-1),m-1)

  14. &nbsp;&nbsp;&nbsp;&nbsp;end for

  15. &nbsp;&nbsp;end if

  16. end function

replacing the test in line 2 with m=1m=1, in which case line 6 only needs to ask whether RR is prime.

Pinch’s later searches [11, 12] go further than PP. They stop at a level where λ(P)\lambda(P) 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 n=PRn=PR 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 nn, is nn a Carmichael number? This is answered in polynomial time by [20], and we discuss how in § 2.3. If the answer is yes, then n−1n-1 is a multiple of λ(n)\lambda(n), which lets us factor nn completely, and so counting its prime factors costs nothing extra. Since RR 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 PP of depth jj, the factoring step recovers the remaining k−jk-j primes. Let tkt_k be the average of k−jk-j over the leaves of W with Pλ(P)>BP\lambda(P)>B, in a search with BB close to SkS_k.

Algorithm P corresponds to always recovering exactly one prime. The gain of W comes from tkt_k being larger. § 3 shows tk<k/2t_k<k/2, and in our computations tkt_k grows slowly with kk (Table 1).

kktkt_kkktkt_kkktkt_kkktkt_k
202.924405.726465.984546.562
243.486415.651476.121556.655
294.145425.805486.253566.752
345.015435.927496.180596.968
365.460445.707506.275606.990
395.396455.936516.404637.211

Table 1. The average number tkt_k of primes recovered by factoring, over all leaves with Pλ(P)>BP\lambda(P)>B, measured during clean passes.

The Carmichael query

We answer line 6 with the algorithm of [20], which uses Fermat tests modulo nn and GCDs to factor RR. 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 T(B,k)\mathcal{T}(B,k). The following two constraints on nodes are what drive everything below.

Lemma 3.1. Let P≠1P \ne1 be a node of T(B,k)\mathcal{T}(B,k) of depth jj. Then

(i) Ppmax⁡(P)k−j≤BP p_{\max}(P)^{k-j} \le B;

(ii) P≤Bj/kP \le B^{j/k}.

Proof. (i) P=P′qP=P' q with q=pmax⁡(P)q=p_{\max}(P) a child of P′P', which has depth j−1j-1, so qk−j+1≤B/P′q^{k-j+1}\le B/P'; that is, Pqk−j≤BPq^{k-j}\le B. (ii) Since P≤pmax⁡(P)jP\le p_{\max}(P)^j, we have P(k−j)/j≤pmax⁡(P)P^{(k-j)/j}\le p_{\max}(P), so by (i) Pk/j=P⋅P(k−j)/j≤Ppmax⁡(P)k−j≤BP^{k/j}=P\cdot P^{(k-j)/j}\le Pp_{\max}(P)^{k-j}\le B. □

An unconditional bound

We want to count the nodes of T(B,k)\mathcal{T}(B,k). By Lemma 3.1(ii), a node of depth jj is a square-free number up to Bj/kB^{j/k} with exactly jj 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 ∏p(1+zp−σ)\prod_p(1+zp^{-\sigma}), with two free parameters σ\sigma and zz. Second, we estimate the logarithm of that product. It is a sum over primes, and the primes that matter lie near pkp_k, where there are about kk of them per unit of p/pkp/p_k. So the sum is kk times an integral, up to o(k)o(k) (Lemma 3.3(b)). Third, we choose zz and σ\sigma to make the bound as small as possible. What comes out is e(c(β)+o(1))ke^{(c(\beta)+o(1))k}, where β\beta measures how far BB exceeds the product of the first kk primes, and c(β)c(\beta) is defined by that optimization (Theorem 3.4).

Lemma 3.2 (Rankin’s bound [23]). Let QQ be a set of primes, x≥1x\ge1, j≥0j\ge0, and let Nj(x;Q)N_j(x;Q) be the number of squarefree n≤xn\le x with ω(n)=j\omega(n)=j and all prime factors in QQ. For every σ≥0\sigma\ge0 and z>0z>0,

Nj(x;Q)≤∑n counted(xn)σ≤xσz−j∏p∈Q(1+zp−σ).N_j(x;Q) \le\sum_{\substack{n\ \mathrm{counted}}}\left(\frac{x}{n}\right)^\sigma\le x^\sigma z^{-j}\prod_{p\in Q}(1+zp^{-\sigma}).

Proof. Each counted nn has (x/n)σ≥1(x/n)^\sigma\ge1. The middle sum is at most xσx^\sigma times the coefficient of zjz^j in ∏p∈Q(1+zp−σ)\prod_{p\in Q}(1+zp^{-\sigma}), and since every coefficient is nonnegative, that coefficient is at most z−jz^{-j} 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

log⁡B=θ(pk)+βk.(1)\log B=\theta(p_k)+\beta k. \tag*{(1)}

Since θ(pk)=klog⁡k+klog⁡log⁡k−k+o(k)\theta(p_k)=k\log k+k\log\log k-k+o(k) is the logarithm of the product of the first kk primes, β\beta measures the excess of the search bound over the smallest conceivable kk-factor product, per prime. For σ>1\sigma>1 put

Aσ=πsin⁡(π/σ),g(σ)=σπ=σπsin⁡πσ∈(0,1).A_\sigma=\frac{\pi}{\sin(\pi/\sigma)},\qquad g(\sigma)=\frac{\sigma}{\pi}=\frac{\sigma}{\pi}\sin\frac{\pi}{\sigma}\in(0,1).

The constant AσA_\sigma is the integral ∫0∞log⁡(1+u−σ) du\int_0^\infty\log(1+u^{-\sigma})\,du 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 c(β)c(\beta) explicit, and its expansion for large σ\sigma is the source of the Hardy–Ramanujan constant in the remark on small excess below. Define, for β≥0\beta\ge0,

c(β)=inf⁡σ>1σ(β−log⁡g(σ)).(2)c(\beta)=\inf_{\sigma>1}\sigma\bigl(\beta-\log g(\sigma)\bigr). \tag*{(2)}

Lemma 3.3. As k→∞k \to\infty:

(a) klog⁡pk−θ(pk)=(1+o(1))kk\log p_k-\theta(p_k)=(1+o(1))k;

(b) for fixed σ>1\sigma>1, ∑plog⁡(1+w(pkp)σ)=(Aσw1/σ+o(1))k\sum_p\log\left(1+w\left(\frac{p_k}{p}\right)^\sigma\right)=(A_\sigma w^{1/\sigma}+o(1))k, the sum over all primes, uniformly for 0<w≤10<w\le1.

Proof. (a) By partial summation, θ(x)−π(x)log⁡x=−∫2xπ(t) dt/t=−(1+o(1))x/log⁡x\theta(x)-\pi(x)\log x=-\int_2^x\pi(t)\,dt/t=-(1+o(1))x/\log x. Take x=pkx=p_k and use pk/log⁡pk∼kp_k/\log p_k\sim k.

(b) Put h(u)=log⁡(1+wu−σ)h(u)=\log(1+wu^{-\sigma}), so the sum is ∑ph(p/pk)\sum_p h(p/p_k). Fix δ∈(0,1)\delta\in(0,1). Primes p≤pk1−δp\le p_k^{1-\delta} contribute O(π(pk1−δ)log⁡pk)=o(k)O(\pi(p_k^{1-\delta})\log p_k)=o(k), since h(u)≤log⁡(1+w)+σlog⁡(1/u)h(u)\le\log(1+w)+\sigma\log(1/u) for u≤1u\le1. Primes p>pk1+δp>p_k^{1+\delta} contribute at most wpkσ∑p>pk1+δp−σ=O(pk1−δ(σ−1))=o(k)w p_k^\sigma\sum_{p>p_k^{1+\delta}}p^{-\sigma}=O(p_k^{1-\delta(\sigma-1)})=o(k). On the middle range, dπ(t)=(1+O(δ)) dt/log⁡pkd\pi(t)=(1+O(\delta))\,dt/\log p_k by the prime number theorem, so the contribution is (1+O(δ))pklog⁡pk∫0∞h(u) du(1+O(\delta))\frac{p_k}{\log p_k}\int_0^\infty h(u)\,du. Integrating by parts, ∫0∞log⁡(1+u−σ) du=σ∫0∞du1+uσ=σπsin⁡(π/σ)\int_0^\infty\log(1+u^{-\sigma})\,du=\sigma\int_0^\infty\frac{du}{1+u^\sigma}=\frac{\sigma\pi}{\sin(\pi/\sigma)}, where the last step substitutes t=uσt=u^\sigma and uses the Beta integral ∫0∞ts−1(1+t)−1 dt=Γ(s)Γ(1−s)\int_0^\infty t^{s-1}(1+t)^{-1}\,dt=\Gamma(s)\Gamma(1-s) with s=1/σs=1/\sigma, together with Euler’s reflection formula. Scaling gives ∫0∞h= ⁣Aσw1/σ\int_0^\infty h=\!A_\sigma w^{1/\sigma}. Let δ→0\delta\to0. Each error term above is bounded independently of w∈(0,1]w\in(0,1], so the estimate is uniform in ww.

Theorem 3.4. Fix β≥0\beta\ge0 and suppose log⁡B≤θ(pk)+βk\log B\le\theta(p_k)+\beta k. Then, as k→∞k\to\infty:

(i) the number of depth-kk nodes of T(B,k)T(B,k) is at most e(c(β)+o(1))ke^{(c(\beta)+o(1))k};

(ii) ∣T(B,k)∣≤e(c(β+1/e)+o(1))k|T(B,k)|\le e^{(c(\beta+1/e)+o(1))k};

(iii) each of N, P, W examines at most e(c(β+1/e)+o(1))ke^{(c(\beta+1/e)+o(1))k} candidates (tree nodes plus arithmetic-progression terms), and every prime it enumerates is at most pkeβkp_ke^{\beta k}.

Proof. Fix σ>1\sigma>1, let 0<w≤10<w\le1, and apply Lemma 3.2 with QQ the set of all primes and z=wpkσz=wp_k^\sigma.

Depth j=αkj=\alpha k. By Lemma 3.1(ii) the depth-jj nodes are counted by Nj(Bj/k)N_j(B^{j/k}), and

log⁡Nj(Bj/k)≤σj(log⁡Bk−log⁡pk)−jlog⁡w+∑plog⁡(1+w(pkp)σ).\log N_j(B^{j/k})\le\sigma j\left(\frac{\log B}{k}-\log p_k\right)-j\log w+\sum_p\log\left(1+w\left(\frac{p_k}{p}\right)^\sigma\right).

By hypothesis and Lemma 3.3(a), log⁡B/k−log⁡pk≤β−1+o(1)\log B/k-\log p_k\le\beta-1+o(1). By Lemma 3.3(b), the right-hand side is at most k[ασ(β−1)−αlog⁡w+Aσw1/σ]+o(k)k[\alpha\sigma(\beta-1)-\alpha\log w+A_\sigma w^{1/\sigma}]+o(k). Choosing w1/σ=αg(σ)w^{1/\sigma}=\alpha g(\sigma) (so w≤1w\le1, since α≤1\alpha\le1 and g(σ)<1g(\sigma)<1; the o(1)o(1) is uniform in α\alpha by Lemma 3.3(b)) and using Aσg(σ)=σA_\sigma g(\sigma)=\sigma gives

log⁡Nj(Bj/k)≤kασ(β+log⁡(1/α)−log⁡g(σ))+o(k).\log N_j(B^{j/k})\le k\alpha\sigma\bigl(\beta+\log(1/\alpha)-\log g(\sigma)\bigr)+o(k).

For α=1\alpha=1 this is kσ(β−log⁡g(σ))+o(k)k\sigma(\beta-\log g(\sigma))+o(k). For general α∈(0,1]\alpha\in(0,1] use αlog⁡(1/α)≤1/e\alpha\log(1/\alpha)\le1/e. Summing over the k+1k+1 depths only adds O(log⁡k)O(\log k). Since σ>1\sigma>1 was arbitrary, (i) and (ii) follow.

Progression terms. For P and W, a leaf PP yields at most $1+B/(P\lambda(P))$ terms (compare [25 (5.3)]). If Pλ(P)>BP\lambda(P)>B this is at most 2, and those leaves are already counted in (ii). Otherwise PP has depth j≥k−2j\ge k-2. Then $\lambda(P)\ge p_{\max}(P)1≥pmax⁡(P)/21 \ge p_{\max}(P)/2, and ρ:=B/(Ppmax⁡(P))≥1\rho:= B/(Pp_{\max}(P)) \ge1 by Lemma 3.1(i). So ρ≤ρσ≤(B/(Ppj))σ\rho\le\rho^\sigma\le(B/(Pp_j))^\sigma, because pmax⁡(P)≥pjp_{\max}(P) \ge p_j. Summing over all squarefree PP with ω(P)=j\omega(P)=j and applying the middle inequality of Lemma 3.2 gives

log⁡∑PBPpmax⁡(P)≤σ(log⁡B−klog⁡pk)+σ(k−j)log⁡pk−σlog⁡pj−jlog⁡w+(Aσw1/σ+o(1))k.\log\sum_P \frac{B}{Pp_{\max}(P)} \le\sigma(\log B-k\log p_k)+\sigma(k-j)\log p_k-\sigma\log p_j-j\log w+\left(A_\sigma w^{1/\sigma}+o(1)\right)k.

Since k−j≤2k-j \le2, this is the α=1\alpha=1 case of the bound above up to O(log⁡k)O(\log k).

Largest prime. A child qq of a depth-(j−1)(j-1) node P′P' satisfies qk−j+1≤B/P′≤B/(p1⋯pj−1)q^{k-j+1}\le B/P'\le B/(p_1\cdots p_{j-1}). Hence (k−j+1)log⁡q≤ϑ(pk)−ϑ(pj−1)+βk≤(k−j+1)log⁡pk+βk(k-j+1)\log q\le\vartheta(p_k)-\vartheta(p_{j-1})+\beta k\le(k-j+1)\log p_k+\beta k, so log⁡q≤log⁡pk+βk\log q\le\log p_k+\beta k.

Remark 3.5. Taking σ=0\sigma=0 in Lemma 3.2 recovers, up to a factor ∣Q∣+1|Q|+1, the binomial count (∣Q∣j)\binom{|Q|}{j} of jj-subsets of a finite set of primes QQ. That count ignores the constraint n≤Bn\le B, which is what actually limits the search. This is why the proof of Theorem 3.4 uses a constant σ>1\sigma>1.

Remark 3.6. Theorem 3.4 uses neither admissibility nor any information about λ\lambda beyond the trivial λ(P)≥pmax⁡(P)−1\lambda(P)\ge p_{\max}(P)-1. It holds for any search of this shape. Admissibility and the actual size of λ(P)\lambda(P) can only improve the constants.

Finding SkS_k without knowing it

Theorem 3.4 bounds the cost of searching T(B,k)\mathcal{T}(B,k) for any BB. It does not assume that B≥SkB\ge S_k. A search with B<SkB<S_k simply finds nothing, and a search with B≥SkB\ge S_k finds SkS_k. To find SkS_k we must therefore choose BB, and we do not know SkS_k in advance. One might worry that the analysis is circular: we use a heuristic to choose BB, and then analyze the search with that BB. It is not, because the procedure we actually run does not need to know SkS_k.

Definition 3.7 (Doubling passes). Let B0B_0 be the product of the first kk odd primes. For i=0,1,2,…i=0,1,2,\ldots, search T(2iB0,k)\mathcal{T}(2^iB_0,k), and stop at the first pass that finds a Carmichael number with kk prime factors. Report the least one found in that pass.

Every Carmichael number is odd and square-free, so Sk≥B0S_k\ge B_0. Pass ii finds SkS_k exactly when 2iB0≥Sk2^iB_0\ge S_k, and so the procedure stops at the least such ii and reports SkS_k. In particular the final bound satisfies B<2SkB<2S_k. (The factor 2 is not special; with any constant ratio r>1r>1 the final bound satisfies B<rSkB<rS_k, which changes β\beta by only (log⁡r)/k(\log r)/k.) If no Carmichael number with kk 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 kk prime factors for every 3≤k≤19 565 2203\le k\le19\,565\,220 [13].

The cost of the procedure is governed by how far SkS_k lies above the product of the first kk primes. Define βk\beta_k by

log⁡Sk=θ(pk)+βkk,\log S_k=\theta(p_k)+\beta_k k,

so that βk\beta_k is the quantity β\beta of (1) evaluated at B=SkB=S_k. This is a property of the sequence SkS_k alone, and it involves no choice on our part.

Corollary 3.8. Let β∗=lim sup⁡k→∞βk\beta^*=\limsup_{k\to\infty}\beta_k, and suppose β∗<∞\beta^*<\infty. Then running any of N, P, W in doubling passes finds SkS_k after examining at most

e(c(β∗+1/e)+o(1))ke^{(c(\beta^*+1/e)+o(1))k}

candidates in total. Since log⁡Sk≥(1+o(1))klog⁡k\log S_k \ge(1+o(1))k\log k, the running time is

T(k)=eO(k)⋅poly⁡(log⁡Sk)=SkO(1/log⁡k).T(k)=e^{O(k)}\cdot\operatorname{poly}(\log S_k)=S_k^{O(1/\log k)}.

Here the per-candidate cost is that of a Korselt check for N\mathbf{N}, a deterministic primality test for P\mathbf{P} (unconditionally polynomial, by [21]), and the factoring step of [20] for W\mathbf{W}. For W\mathbf{W} this bound is unconditional for the expected running time of the randomized factoring step; see § 2.3.

Proof. Fix ε>0\varepsilon>0. For all large kk we have βk≤β∗+ε\beta_k\le\beta^*+\varepsilon. Every pass has B<2SkB<2S_k, so

log⁡B<θ(pk)+βkk+log⁡2≤θ(pk)+(β∗+2ε)k\log B<\theta(p_k)+\beta_k k+\log2\le\theta(p_k)+(\beta^*+2\varepsilon)k

for large kk. By Theorem 3.4(iii), each pass examines at most e(c(β∗+2ε+1/e)+o(1))ke^{(c(\beta^*+2\varepsilon+1/e)+o(1))k} candidates. The number of passes is at most 1+log⁡2(Sk/B0)1+\log_2(S_k/B_0). Since log⁡B0=θ(pk+1)−log⁡2≥θ(pk)−log⁡2\log B_0=\theta(p_{k+1})-\log2\ge\theta(p_k)-\log2, this is at most 1+((β∗+ε)k+log⁡2)/log⁡2=O(k)1+((\beta^*+\varepsilon)k+\log2)/\log2=O(k). The factor O(k)O(k) is absorbed into the o(1)o(1) in the exponent. Finally, cc is continuous, so we may let ε→0\varepsilon\to0. The per-candidate cost is polynomial in log⁡Sk=O(klog⁡k)\log S_k=O(k\log k), which is eO(log⁡k)e^{O(\log k)}.

The bound in Corollary 3.8 is output-sensitive. It is stated in terms of the answer SkS_k, through β∗\beta^*, but the procedure itself uses no information about SkS_k. The only hypothesis is that β∗\beta^* is finite, which is a statement about the size of SkS_k 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 pkeβkp_ke^{\beta_k}, and a table of the primes up to that size costs e(β+o(1))ke^{(\beta+o(1))k}. Since c(β)>βc(\beta)>\beta, this does not change the exponent.

In practice we start at a bound B0B_0 given by a heuristic formula, rather than at the product of the first kk odd primes. This changes only which of the cheap early passes are skipped. If the formula undershoots SkS_k, nothing in the analysis changes. If it overshoots, say log⁡B0=log⁡Sk+δk\log B_0=\log S_k+\delta k, then the single pass costs e(c(βk+δ+1/e)+o(1))ke^{(c(\beta_k+\delta+1/e)+o(1))k}. So a heuristic that overshoots by a factor of eo(k)e^{o(k)} does not change the exponent.

It remains to say why β∗\beta^* should be finite. For k≥3k\ge3, let qq be the least number such that the interval (q/2,q](q/2,q] contains kk primes, and let U(k)U(k) be the product of those kk primes.

Conjecture 3.9. Sk<U(k)S_k<U(k) for all k≥3k\ge3.

Proposition 3.10. log⁡U(k)≤θ(pk)+(1+log⁡2+o(1))k\log U(k)\le\theta(p_k)+(1+\log2+o(1))k. Consequently, Conjecture 3.9 implies β∗≤1+log⁡2\beta^*\le1+\log2, and so T(k)=eO(k)T(k)=e^{O(k)}.

Proof. By the prime number theorem π(q)−π(q/2)∼q/(2log⁡q)\pi(q)-\pi(q/2)\sim q/(2\log q), so this qq satisfies q∼2klog⁡kq\sim2k\log k. Every factor of U(k)U(k) is at most qq, so log⁡U(k)≤klog⁡q=klog⁡k+klog⁡log⁡k+klog⁡2+o(k)\log U(k)\le k\log q=k\log k+k\log\log k+k\log2+o(k). Compare with θ(pk)=klog⁡k+klog⁡log⁡k−k+o(k)\theta(p_k)=k\log k+k\log\log k-k+o(k).

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: c(β)c(\beta) is the true constant for the square-free numbers with kk 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 σ\sigma and zz 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 #{n≤x:ω(n)=ν}\#\{n \le x : \omega(n) = \nu\} holds for ν≤log⁡x/(log⁡log⁡x)2\nu\le\log x/(\log\log x)^2, while we need ν=k∼log⁡x/log⁡log⁡x\nu= k \sim\log x/\log\log x. 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 pkp_k, 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 pkp_k, the prime number theorem is all we need. Erdős and Nicolas [24] used the same kind of construction for the case βk=log⁡pk+1\beta_k = \log p_{k+1}.

Write H(t)=−tlog⁡t−(1−t)log⁡(1−t)H(t) = -t\log t - (1-t)\log(1-t) for 0≤t≤10 \le t \le1.

Theorem 3.11. Fix β>0\beta> 0, and let Mk(β)M_k(\beta) be the number of square-free n≤eθ(pk)+βkn \le e^{\theta(p_k)+\beta k} with ω(n)=k\omega(n) = k. Then log⁡Mk(β)=(c(β)+o(1))k\log M_k(\beta) = (c(\beta) + o(1))k as k→∞k \to\infty.

The upper bound is the case α=1\alpha= 1 of the proof of Theorem 3.4, which counts all square-free nn with ω(n)=k\omega(n) = k and never uses admissibility. The lower bound rests on two lemmas.

Lemma 3.12. Fix β>0\beta> 0. The infimum defining c(β)c(\beta) is attained at some σ0>1\sigma_0 > 1. Put w0=g(σ0)σ0w_0 = g(\sigma_0)^{\sigma_0} and f(u)=1/(1+uσ0/w0)f(u) = 1/(1 + u^{\sigma_0}/w_0) for u>0u > 0. Then

(a)∫0∞f(u) du=1,(b)∫0∞f(u)log⁡u du=β−1,\text{(a)}\quad\int_0^\infty f(u)\,du = 1,\qquad\text{(b)}\quad\int_0^\infty f(u)\log u\,du = \beta- 1,
(c)∫0∞H(f(u)) du=c(β).\text{(c)}\quad\int_0^\infty H(f(u))\,du = c(\beta).

Proof. Let Φ(σ)=σ(β−log⁡g(σ))\Phi(\sigma) = \sigma(\beta- \log g(\sigma)). As σ→1+\sigma\to1^+ we have g(σ)→0g(\sigma) \to0, and Φ(σ)≥σβ\Phi(\sigma) \ge\sigma\beta since g<1g < 1, so Φ→∞\Phi\to\infty at both ends of (1,∞)(1,\infty). It is continuous, so its infimum is attained at some σ0\sigma_0.

For σ>1\sigma> 1 and w>0w > 0 put fσ,w(u)=wu−σ/(1+wu−σ)f_{\sigma,w}(u) = wu^{-\sigma}/(1 + wu^{-\sigma}), so that f=fσ0,w0f = f_{\sigma_0,w_0}, and put

I(σ,w)=∫0∞log⁡(1+wu−σ) du=Aσw1/σ,F(σ,w)=σ(β−1)−log⁡w+I(σ,w),I(\sigma,w) = \int_0^\infty\log(1 + wu^{-\sigma})\,du = A_\sigma w^{1/\sigma},\qquad F(\sigma,w) = \sigma(\beta- 1) - \log w + I(\sigma,w),

where the closed form for II is the computation in the proof of Lemma 3.3(b). For fixed σ\sigma, FF is a convex function of log⁡w\log w, minimized where w1/σ=σ/Aσ=g(σ)w^{1/\sigma} = \sigma/A_\sigma= g(\sigma), and there F=Φ(σ)F = \Phi(\sigma). So Φ(σ)=min⁡wF(σ,w)\Phi(\sigma) = \min_w F(\sigma,w), with minimizer w∗(σ)=g(σ)σw^*(\sigma) = g(\sigma)^\sigma, and w∗(σ0)=w0w^*(\sigma_0) = w_0.

(a) ∫0∞fσ,w du=∂I/∂log⁡w=w1/σAσ/σ\int_0^\infty f_{\sigma,w}\,du = \partial I/\partial\log w = w^{1/\sigma}A_\sigma/\sigma, which is 11 at w=w∗(σ)w = w^*(\sigma).

(b) Differentiating under the integral sign (by dominated convergence, for σ\sigma in a compact subset of (1,∞)(1,\infty)), ∂I/∂σ=−∫0∞fσ,w(u)log⁡u du\partial I/\partial\sigma= -\int_0^\infty f_{\sigma,w}(u)\log u\,du. Since ∂F/∂w=0\partial F/\partial w = 0 at w=w∗(σ)w = w^*(\sigma), we get Φ′(σ)=β−1−∫0∞fσ,w∗(σ)(u)log⁡u du\Phi'(\sigma) = \beta- 1 - \int_0^\infty f_{\sigma,w^*(\sigma)}(u)\log u\,du. At the minimum Φ′(σ0)=0\Phi'(\sigma_0) = 0, which is (b).

(c) Write a=w0u−σ0a = w_0u^{-\sigma_0}, so f=a/(1+a)f = a/(1+a), log⁡f=log⁡a−log⁡(1+a)\log f = \log a-\log(1+a), and log⁡(1−f)=−log⁡(1+a)\log(1-f) = -\log(1+a). Then

H(f)=log⁡(1+a)−flog⁡a=log⁡(1+w0u−σ0)+f(u)(σ0log⁡u−log⁡w0).H(f) = \log(1+a) - f\log a = \log(1 + w_0u^{-\sigma_0}) + f(u)(\sigma_0\log u - \log w_0).

Integrating and using (a) and (b), ∫0∞H(f)=I(σ0,w0)+σ0(β−1)−log⁡w0=F(σ0,w0)=c(β)\int_0^\infty H(f) = I(\sigma_0,w_0) + \sigma_0(\beta- 1) - \log w_0 = F(\sigma_0,w_0) = c(\beta). □

The integrals in Lemma 3.12 converge absolutely. Near 00 we have f≤1f \le1 and H≤log⁡2H \le\log2, and for large uu we have f(u)≤w0u−σ0f(u) \le w_0u^{-\sigma_0} and H(f(u))=O(u−σ0log⁡u)H(f(u)) = O(u^{-\sigma_0}\log u), with σ0>1\sigma_0 > 1.

Lemma 3.13. Fix β>0\beta> 0 and η>0\eta> 0. For all large kk there are at least e(c(β)−η)ke^{(c(\beta)-\eta)k} square-free nn with ω(n)=k\omega(n)=k and ∣log⁡n−θ(pk)−βk∣≤ηk\lvert\log n-\theta(p_k)-\beta k\rvert\leq\eta k.

Proof. Let ff be as in Lemma 3.12. Choose parameters 0<ε<1<2<U0<\varepsilon<1<2<U and δ>0\delta>0, in that order, as described at the end of the proof. Let I1,…,ILI_1,\ldots,I_L be the consecutive intervals of length δ\delta that partition [ε,U)[\varepsilon,U), taking (U−ε)/δ(U-\varepsilon)/\delta to be an integer, and let uiu_i be the left endpoint of IiI_i. Every nn we build is the product of all primes p≤εpkp\leq\varepsilon p_k and, for each ii, a set of mim_i primes pp with p/pk∈Iip/p_k\in I_i. These primes are distinct, so nn is square-free. Let NiN_i be the number of primes pp with p/pk∈Iip/p_k\in I_i, and let s=π(εpk)s=\pi(\varepsilon p_k). Since the IiI_i lie in the fixed range [ε,U][\varepsilon,U], the prime number theorem and pk/log⁡pk∼kp_k/\log p_k\sim k give Ni=δk(1+o(1))N_i=\delta k(1+o(1)), uniformly in ii, and s=εk(1+o(1))s=\varepsilon k(1+o(1)).

Choice of the mim_i. Start from mi0=⌊f(ui)Ni⌋m_i^0=\lfloor f(u_i)N_i\rfloor. Since ff is decreasing, δ∑if(ui)\delta\sum_i f(u_i) differs from ∫εUf\int_\varepsilon^U f by at most δ\delta, so by Lemma 3.12(a)

s+∑imi0=k(1+ε−∫0εf−∫U∞f+O(δ))+o(k).s+\sum_i m_i^0=k\left(1+\varepsilon-\int_0^\varepsilon f-\int_U^\infty f+O(\delta)\right)+o(k).

So the defect d=k−s−∑imi0d=k-s-\sum_i m_i^0 satisfies ∣d∣≤τk+o(k)\lvert d\rvert\leq\tau k+o(k), where τ=ε+∫0∞f+δ\tau=\varepsilon+\int_0^\infty f+\delta. Let JJ be the set of ii with Ii⊂[1,2]I_i\subset[1,2], and let ρ=min⁡(f(2),1−f(1))>0\rho=\min(f(2),1-f(1))>0. For i∈Ji\in J the block has at least ρNi−1\rho N_i-1 unused primes and at least ρNi−1\rho N_i-1 chosen ones. If τ<ρ/4\tau<\rho/4, we can absorb dd by changing each mi0m_i^0 with i∈Ji\in J by at most 2τNi+12\tau N_i+1, in the direction of the sign of dd. This gives mim_i with 0≤mi≤Ni0\leq m_i\leq N_i and s+∑imi=ks+\sum_i m_i=k, so that every nn built has ω(n)=k\omega(n)=k, and with ∣mi/Ni−f(ui)∣≤1/Ni\lvert m_i/N_i-f(u_i)\rvert\leq1/N_i for i∉Ji\notin J and ∣mi/Ni−f(ui)∣≤2τ+2/Ni\lvert m_i/N_i-f(u_i)\rvert\leq2\tau+2/N_i for i∈Ji\in J.

Counting. The number of such nn is ∏i(Nimi)\prod_i\binom{N_i}{m_i}, and log⁡(Nm)≥NH(m/N)−log⁡(N+1)\log\binom{N}{m}\geq NH(m/N)-\log(N+1). Let μ\mu be a modulus of continuity for HH on [0,1][0,1]. Then

log⁡∏i(Nimi)≥∑iNiH(f(ui))−kμ(3τ)−O(Llog⁡k)=k(δ∑iH(f(ui))−μ(3τ))+o(k).\begin{aligned} \log\prod_i\binom{N_i}{m_i}\geq\sum_iN_iH(f(u_i))-k\mu(3\tau)-O(L\log k) \\ &=k\left(\delta\sum_iH(f(u_i))-\mu(3\tau)\right)+o(k). \end{aligned}

Here the term kμ(3τ)k\mu(3\tau) comes from the blocks in JJ, which contain at most (1+o(1))k(1+o(1))k primes in all, and every other block loses only Niμ(1/Ni)=O(log⁡k)N_i\mu(1/N_i)=O(\log k). As δ→0\delta\to0, δ∑iH(f(ui))→∫εUH(f)\delta\sum_iH(f(u_i))\to\int_\varepsilon^U H(f), and by Lemma 3.12(c) this is c(β)c(\beta) minus the two tails ∫0εH(f)≤εlog⁡2\int_0^\varepsilon H(f)\leq\varepsilon\log2 and ∫U∞H(f)\int_U^\infty H(f).

Size. Since exactly kk primes divide nn,

log⁡n−θ(pk)=(klog⁡pk−θ(pk))+∑p≤εpklog⁡ppk+∑i∑p/pk∈Iilog⁡ppk.\log n-\theta(p_k)=\left(k\log p_k-\theta(p_k)\right)+\sum_{p\leq\varepsilon p_k}\log\frac{p}{p_k}+\sum_i\sum_{\substack{p/p_k\in I_i}}\log\frac{p}{p_k}.

The first term is k+o(k)k+o(k) by Lemma 3.3(a). For the second, the partial summation in the proof of Lemma 3.3(a), applied at x=εpkx=\varepsilon p_k, gives

∑p≤εpklog⁡ppk=θ(εpk)−π(εpk)log⁡pk=−ε(1+log⁡(1/ε))k+o(k).\sum_{p\leq\varepsilon p_k}\log\frac{p}{p_k}=\theta(\varepsilon p_k)-\pi(\varepsilon p_k)\log p_k=-\varepsilon(1+\log(1/\varepsilon))k+o(k).

For the third, each prime counted in IiI_i has ∣log⁡(p/pk)−log⁡ui∣≤δ/ε\lvert\log(p/p_k)-\log u_i\rvert\leq\delta/\varepsilon, and there are at most kk of them. Also ∣log⁡ui∣≤Λ=max⁡(log⁡(1/ε),log⁡U)\lvert\log u_i\rvert\leq\Lambda=\max(\log(1/\varepsilon),\log U) for all ii, and ∣log⁡ui∣≤log⁡2|\log u_i| \le\log2 for i∈Ji \in J. So the third term is

∑imilog⁡ui+O(δεk)=kδ∑if(ui)log⁡ui+O(τk+LΛ+δεk)+o(k),\sum_i m_i \log u_i + O\left(\frac{\delta}{\varepsilon}k\right) = k\delta\sum_i f(u_i)\log u_i + O\left(\tau k + L\Lambda+ \frac{\delta}{\varepsilon}k\right) + o(k),

and δ∑if(ui)log⁡ui→∫εUflog⁡u\delta\sum_i f(u_i)\log u_i \to\int_{\varepsilon}^{U} f\log u as δ→0\delta\to0. By Lemma 3.12(b), ∫εUflog⁡u=β−1−∫0εflog⁡u−∫U∞flog⁡u\int_{\varepsilon}^{U} f\log u = \beta- 1 - \int_0^{\varepsilon} f\log u - \int_U^\infty f\log u, and both tails tend to 00 as ε→0\varepsilon\to0 and U→∞U \to\infty. Putting the three terms together, log⁡n−θ(pk)−βk\log n-\theta(p_k)-\beta k is kk times a quantity that tends to 00 as ε→0\varepsilon\to0, then U→∞U \to\infty, then δ→0\delta\to0, plus o(k)o(k).

Choice of parameters. Given η\eta, choose ε\varepsilon small and then UU large, so that ε+∫U∞f<ρ/8\varepsilon+\int_U^\infty f<\rho/8 and so that ε(1+log⁡(1/ε))\varepsilon(1+\log(1/\varepsilon)), the four tails, and μ(3τ)\mu(3\tau) are all small compared with η\eta. Then choose δ\delta small compared with εη\varepsilon\eta and with ρ\rho. For all large kk, 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 cc is an infimum of functions that are affine in β\beta, so it is concave, and hence continuous, on (0,∞)(0,\infty). Given η∈(0,β/2)\eta\in(0,\beta/2), apply Lemma 3.13 with β−η\beta-\eta in place of β\beta and η/2\eta/2 in place of η\eta. Every nn it produces has log⁡n≤θ(pk)+(β−η/2)k\log n\le\theta(p_k)+(\beta-\eta/2)k, so log⁡Mk(β)≥(c(β−η)−η/2)k\log M_k(\beta)\ge(c(\beta-\eta)-\eta/2)k for all large kk. Let η→0\eta\to0. □

Remark 3.14 (Small excess). As β→0\beta\to0, we have c(β)∼π2β/3c(\beta)\sim\pi\sqrt{2\beta/3}, the Hardy–Ramanujan constant [29]. That is what one expects if the primes near pkp_k were evenly spaced, since then the numbers counted in Theorem 3.11 would correspond to partitions of about βk2\beta k^2. Erdős and Nicolas [24 p. 10] use the same partition heuristic.

The number of primes recovered by factoring.

Proposition 3.15. For k>4k>4, every leaf of WW has fewer than k/2k/2 primes remaining. In particular tk<k/2t_k<k/2.

Proof. Let P≠1P\ne1 be a leaf of depth jj, so that k−jk-j primes remain. If the leaf arose from the rule k−j≤2k-j\le2, then k−j≤2<k/2k-j\le2<k/2. Otherwise Pλ(P)>BP\lambda(P)>B. By Lemma 3.1(i), and since λ(P)∣φ(P)\lambda(P)\mid\varphi(P) gives λ(P)<P\lambda(P)<P,

pmax⁡(P)k−j≤B/P<λ(P)<P≤pmax⁡(P)j.p_{\max}(P)^{k-j}\le B/P<\lambda(P)<P\le p_{\max}(P)^j.

Hence k−j<jk-j<j, that is, k−j<k/2k-j<k/2. □

Table 1 shows tkt_k as measured in our computations. It grows slowly with kk, from about 3 at k=20k=20 to about 7 at k=63k=63, and stays far below the bound k/2k/2 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 tkt_k keeps growing.

The bound BB in each run was close to, but not exactly, SkS_k, and the runs for different kk used different versions of our code. This may account for the small departures from monotonicity (for example at k=36k=36 and k=44k=44).

Where N, P, and W differ.

One might expect the three algorithms to differ the way (SkN)(S_k^N), (Sk−1P)(S_{k-1}^P), and (Sk−tkW)(S_{k-t_k}^W) do, where SN>SP>SWS_N>S_P>S_W 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 n≤Bn\le B (Remark 3.5), which the search enforces at every node through the bound (B/P)1/m(B/P)^{1/m} 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 (Nimi)\binom{N_i}{m_i} over ranges of primes near pkp_k. The smallest primes are nearly forced, and almost all of the freedom lies in the Θ(k)\Theta(k) primes near pkp_k. 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 tkt_k for W.

Algorithm P removes only the largest prime from explicit enumeration. Algorithm W removes the largest tkt_k primes. By Proposition 3.15, tk<k/2t_k<k/2. Over our range tkt_k grows, but tk/kt_k/k falls slowly, from about 0.15 for k≤36k\le36 to 0.11 at k=63k=63 (Table 1). This is consistent with tk=o(k)t_k=o(k), but the range is too short to establish it.

Let TN(k)T_N(k), TP(k)T_P(k), and TW(k)T_W(k) be the numbers of candidates that the three algorithms examine in a search with BB close to SkS_k.

Heuristic 3.16. If tk=o(k)t_k=o(k), then log⁡TN(k)\log T_N(k), log⁡TP(k)\log T_P(k), and log⁡TW(k)\log T_W(k) agree up to o(k)o(k), and all are at most (c(βk)+o(1))k(c(\beta_k)+o(1))k, where βk\beta_k is defined by log⁡Sk=θ(pk)+βkk\log S_k=\theta(p_k)+\beta_k k. The advantage of W over N comes from the choices of the largest tkt_k primes, which contribute eo(k)e^{o(k)} 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 e(c(β+1/e)+o(1))ke^{(c(\beta+1/e)+o(1))k}. The heuristic assumes that, at exponential scale, interior nodes are no more numerous than leaves. This is plausible, since an interior node of depth αk\alpha k fixes only small primes, which contribute little to the count, and leaves the primes near pkp_k 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 tkt_k. If tkt_k could be shown to grow linearly in kk (which tk<k/2t_k<k/2 does not exclude), W would improve the leading constant itself. The size of λ(P)\lambda(P) at the leaves controls tkt_k, through R<λ(P)R<\lambda(P). If we had better heuristics for the size of λ(P)\lambda(P) when PP is a product of many small admissible primes, we could estimate tkt_k, 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 n≤xn\le x with λ(n)≤y\lambda(n)\le y.

Admissibility

The tree T(B,k)\mathcal{T}(B,k) 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 β>1+log⁡2\beta> 1 + \log2, 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 kk.

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 p<qp<q are primes in an interval (Q/2,Q](Q/2,Q], then q≢1(modp)q \not\equiv1 \pmod{p}, since q≡1(modp)q \equiv1 \pmod{p} would force q≥2p+1>Qq \ge2p+1>Q. So any set of primes in such an interval is pairwise admissible, and every product of kk of them is a depth-kk node of T(B,k)T(B,k) once it is at most BB. Fix ε>0\varepsilon>0 and take Q=2(1+ε)klog⁡kQ=2(1+\varepsilon)^k\log k. By the prime number theorem the interval (Q/2,Q](Q/2,Q] contains (1+ε+o(1))k(1+\varepsilon+o(1))k primes, and any kk of them have product at most QkQ^k, where

log⁡Qk=θ(pk)+(1+log⁡2+log⁡(1+ε)+o(1))k.\log Q^k = \theta(p_k) + (1+\log2+\log(1+\varepsilon)+o(1))k.

Hence, for every β>1+log⁡2\beta>1+\log2, choosing ε\varepsilon with log⁡(1+ε)<β−1−log⁡2\log(1+\varepsilon)<\beta-1-\log2 shows that T(B,k)T(B,k) has at least (1+ε+o(1))k=eΩ(k)(1+\varepsilon+o(1))^k = e^{\Omega(k)} nodes of depth kk. Together with (a), the tree has size eΘ(k)e^{\Theta(k)} in this range.

(c) We do not know how admissibility affects the constant c(β)c(\beta). The density of primes admissible to PP depends on which small primes divide PP, 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 pp in PP makes every prime q≡1(modp)q\equiv1\pmod p inadmissible, which is a proportion 1/(p−1)1/(p-1) of all primes. For p=3p=3 this is half of them. For the search, this is pruning, and the subtree below pp is thin. For the products themselves, it means that a product containing pp must be larger, as the next result shows.

Proposition 3.18 (Small primes force larger products). Let DD be a fixed finite set of odd primes, and put

δ(D)=∏p∈Dp−2p−1.\delta(D)=\prod_{p\in D}\frac{p-2}{p-1}.

As k→∞k\to\infty, every depth-kk node nn of T(B,k)T(B,k) that is divisible by every prime in DD satisfies

log⁡n≥θ(pk)+klog⁡(1/δ(D))+o(k).\log n\ge\theta(p_k)+k\log(1/\delta(D))+o(k).

In particular, if a fixed prime pp divides SkS_k, then βk≥log⁡p−1p−2−o(1)\beta_k\ge\log\frac{p-1}{p-2}-o(1).

Proof. Let M=∏p∈DpM=\prod_{p\in D}p, and let QDQ_D be the set of primes q∤Mq\nmid M with q≢1(modp)q\not\equiv1\pmod p for every p∈Dp\in D. Let qq be a prime factor of nn not in DD, and let p∈Dp\in D. If q>pq>p, then q≢1(modp)q\not\equiv1\pmod p because nn is admissible; if q<pq<p, then q≡1(modp)q\equiv1\pmod p is impossible. So every prime factor of nn outside DD lies in QDQ_D. The set QDQ_D is the set of primes in ∏p∈D(p−2)\prod_{p\in D}(p-2) of the φ(M)=∏p∈D(p−1)\varphi(M)=\prod_{p\in D}(p-1) reduced residue classes modulo MM. By the prime number theorem for arithmetic progressions, it contains (δ(D)+o(1))π(x)(\delta(D)+o(1))\pi(x) primes up to xx. Hence its mm-th element qmq_m satisfies log⁡qm=log⁡m+log⁡log⁡m+log⁡(1/δ(D))+o(1)\log q_m = \log m + \log\log m + \log(1/\delta(D)) + o(1). Since nn has at least k−∣D∣k-|D| prime factors in QD\mathbb{Q}_D,

log⁡n≥∑m≤k−∣D∣log⁡qm=klog⁡k+klog⁡log⁡k−k+klog⁡(1/δ(D))+o(k),\log n \ge\sum_{m\le k-|D|} \log q_m = k\log k + k\log\log k-k+k\log(1/\delta(D))+o(k),

and the first three terms are θ(pk)+o(k)\theta(p_k)+o(k). For the last claim, SkS_k is a depth-kk node of T(Sk,k)T(S_k,k). □

So a fixed small prime pp adds about klog⁡p−1p−2k\log\frac{p-1}{p-2} to log⁡n\log n. This is klog⁡2k\log2 for p=3p=3, klog⁡(4/3)k\log(4/3) for p=5p=5, and roughly k/(p−2)k/(p-2) in general. Including pp saves only the ratio of pp to the prime it displaces, which is eO(log⁡k)e^{O(\log k)}. The proposition alone does not exclude any prime from SkS_k in our range, since βk≥0.80\beta_k\ge0.80 there and log⁡2≈0.693\log2\approx0.693. But it does show that if β∗<log⁡p−1p−2\beta^*<\log\frac{p-1}{p-2}, then p∤Skp\nmid S_k for all large kk.

Theory and practice

The bounds above are far from what we observe. For the new values, βk\beta_k falls from about 0.88 at k=40k=40 to about 0.81 at k=64k=64 (Table 2). At β=0.81\beta=0.81 we have c(β)≈2.49c(\beta)\approx2.49, so Theorem 3.4 allows on the order of e2.49ke^{2.49k} nodes of depth kk. At a given kk we can also evaluate the bound of Lemma 3.2 directly. For B=1.05SkB=1.05S_k, minimizing it numerically over σ\sigma and zz gives about 104110^{41} at k=40k=40 and 105110^{51} at k=50k=50. In our clean passes with the same BB, the number of leaves with Pλ(P)>BP\lambda(P)>B was about 3.0⋅1083.0\cdot10^8 at k=40k=40 and 1.0⋅10111.0\cdot10^{11} at k=50k=50. That is growth like e0.58ke^{0.58k}, and the counts are smaller than the bound by more than thirty orders of magnitude.

kkdigitspmin⁡p_{\min}pmax⁡p_{\max}βk\beta_kkkdigitspmin⁡p_{\min}pmax⁡p_{\max}βk\beta_k
40841714090.881531181912970.838
4187177690.891541211910510.845
42891711530.87955124199530.839
4392176410.869561261910090.832
4495178590.892571291911230.827
4597176010.873581321911230.817
46100177570.872591341913210.817
47102176910.860601371918730.817
481051710090.849611401926890.801
491081712890.864621431914710.806
50110179370.856631451912010.807
51113196910.845641481915790.807
521161910510.857

Table 2. The new values of SkS_k: the number of decimal digits, the least and greatest prime factors, and βk\beta_k, defined by log⁡Sk=θ(pk)+βkk\log S_k = \theta(p_k) + \beta_k k.

The data do support Conjecture 3.9. For every 40≤k≤6440\le k\le64, SkS_k is smaller than U(k)U(k), by a factor of about 101810^{18} at k=40k=40, growing to about 103010^{30} at k=64k=64.

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 kk, while the leaves of WW lie about tkt_k levels higher. We have not measured these two effects separately. Proposition 3.18 shows that each small prime in PP prunes the tree heavily, and PP contains many small primes. The lower bound of Remark 3.17(b) does not reach our data either, since it needs β>1+log⁡2≈1.69\beta>1+\log2\approx1.69. So the exponential order eΘ(k)e^{\Theta(k)} is proved only for larger β\beta 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 SkS_k with the least cyclic number with kk prime factors, and we look at one visible effect of it, the least prime factor of SkS_k.

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 λ(P)\lambda(P) (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 PP as a GMP integer times a 64-bit accumulator. Appending qq multiplies only the accumulator, and the accumulator is folded into the GMP integer when the product would overflow. The same is done for λ(P)\lambda(P). We also keep λ(P)\lambda(P) 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, lcm⁡(λ(P),q−1)=λ(P)(q−1)/gcd⁡(λ(P),q−1)\operatorname{lcm}(\lambda(P),q-1)=\lambda(P)(q-1)/\operatorname{gcd}(\lambda(P),q-1) needs a gcd at every interior node, and for the larger kk the number λ(P)\lambda(P) does not fit in a machine word. Instead we precompute the factorization of q−1q-1 for every prime qq in range. Line 13 is then a merge of two short sorted lists, keeping the larger exponent of each prime, and λ(P)\lambda(P) is multiplied only by the prime powers that grow. The merge is faster than Euclid’s algorithm. Together with the additive update of log⁡λ(P)\log\lambda(P) described below, it saved 6 to 11 percent of the total running time for 20≤k≤3420 \le k \le34. Often (q−1)∣λ(P)(q-1)\mid\lambda(P), and then the child shares the parent’s λ\lambda and nothing is copied.

Euclid’s algorithm still appears once per leaf, in line 3, where r⋆=P−1 mod λ(P)r^\star=P^{-1}\bmod\lambda(P) is computed by a modular inversion. We do not know how to avoid it. Can r⋆r^\star be computed incrementally from the parent, or amortized over the leaves below a common ancestor? The difficulty is that the modulus changes from λ(P)\lambda(P) to λ(Pq)\lambda(Pq) 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 PP. A node carries PP, λ(P)\lambda(P) in factored form, and the bit vector of admissible primes described below, but no list of the primes in PP. The search never needs one. Admissibility is tracked by the bit vector, and λ(P)\lambda(P) is updated from the factorization of q−1q-1 alone. We need the factorization of n=PRn=PR 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 RR into its primes, and we recover the primes of PP by dividing PP by the primes up to pmax⁡(P)p_{\max}(P).

We perform the test Pλ(P)>BP\lambda(P)>B in line 2 with floating-point logarithms. Both log⁡P\log P and log⁡λ(P)\log\lambda(P) are updated additively in line 13, using a table of log⁡q\log q. 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 kk in Table 1, constants as large as 5 could be used with no major change to the behavior of the algorithm. Replacing 2 by cc affects only nodes that reach cc or fewer remaining primes while Pλ(P)≤BP\lambda(P)\le B. But almost every leaf with Pλ(P)>BP\lambda(P)>B has at least 5 primes remaining; those with 4 or fewer make up less than 1% of the leaves for each k≥56k\ge56 that we measured. For small kk, where tkt_k 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 qq we precompute a mask MqM_q that clears every r≡1(modq)r\equiv1\pmod q. Each node carries its own bit vector of primes admissible to PP. In line 13, the child’s vector is the parent’s vector ANDed with MqM_q, and only the words above qq need to be touched. Line 12 then reduces to repeatedly finding the next set bit (a count-trailing-zeros instruction) until the prime exceeds (B/P)1/m(B/P)^{1/m}. We compute that bound once per node, with one call to exp, and recompute it only when BB 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 CkC_k in § 6 shows that, for every 26≤k≤6426 \le k \le64, no cyclic number with kk prime factors that is divisible by 3 or by 5 is less than SkS_k. For 3 the margin is wide: the least cyclic number with kk prime factors divisible by 3 exceeds SkS_k by a factor of more than 10710^7 for k≥40k \ge40. Second, if (B/P)1/m(B/P)^{1/m} 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 q≤500q \le500 we skip the intermediate level and append two primes at once. At start-up we tabulate, for each such q1q_1, the primes q2>q1q_2 > q_1 admissible to q1q_1, together with the combined mask Mq1∧Mq2M_{q_1} \wedge M_{q_2} and the factorization of lcm⁡(q1−1,q2−1)\operatorname{lcm}(q_1-1,q_2-1). A node then creates its grandchildren Pq1q2Pq_1q_2 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 pmax⁡(P)p_{\max}(P). The cofactor RR is a product of mm primes, each larger than pp, so we may start at the least term exceeding pmp^m. When the search is run in passes with increasing bounds (see Section 4.8), we also start above B′/PB'/P, where B′B' is the bound of the previous pass.

If Pλ(P)>BP\lambda(P) > B, then the loop in lines 5–10 runs at most once. Indeed, any completion satisfies 0<R≤B/P<λ(P)0 < R \le B/P < \lambda(P) and R≡r⋆(modλ(P))R \equiv r^\star\pmod{\lambda(P)}, so R=r⋆R = r^\star. The only candidate is Pr⋆Pr^\star, and it is a candidate only if r⋆>pr^\star> p and Pr⋆≤BPr^\star\le B; the next term already has P(r⋆+λ(P))>Pλ(P)>BP(r^\star+\lambda(P)) > P\lambda(P) > B. We check log⁡P+log⁡r⋆≤log⁡B\log P+\log r^\star\le\log B in floating point before forming Pr⋆Pr^\star, and we discard r⋆r^\star unless gcd⁡(r⋆,P)=1\gcd(r^\star,P)=1.

In every computation reported here, this is the only kind of leaf that mattered. The other branch of line 2, a leaf with m≤2m \le2 and Pλ(P)≤BP\lambda(P) \le B, 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 ℓ≤\ell\le MAX PRIME that is at most pp or is not admissible to PP, we mark the terms divisible by ℓ\ell, 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 RR. Write n−1=2sdn-1=2^s d with dd odd. Since (p−1)∣(n−1)(p-1)\mid(n-1) for every p∣Pp\mid P by construction, bn≡b(modP)b^n \equiv b \pmod P holds automatically. So we need only check bn≡b(modR)b^n \equiv b \pmod R, and all of the arithmetic can be done modulo RR instead of modulo nn. If m>1m>1 and RR is prime, we reject at once. Otherwise, for b=2,3,5,…b=2,3,5,\ldots we compute bd,b2d,…,b2s−1d(modR)b^d,b^{2d},\ldots,b^{2^{s-1}d}\pmod R, reject if bn≢b(modR)b^n \not\equiv b\pmod R, and split each un-factored divisor of RR by gcd(D,b2d+1)(D,b^{2^d}+1). We stop when every part is prime, and accept if there are exactly mm parts qq, each with (q−1)∣(n−1)(q-1)\mid(n-1).

One might ask “Why not trial divide RR first?” We tried this, and it does not help. The exponentiations that build confidence that nn is a Carmichael number (and so warrant spending computational effort on factoring RR) produce the factors of RR as a byproduct. By the time enough bases have passed, RR 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 kk 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 PP, λ(P)\lambda(P), the bit vector of admissible primes, the bound (B/P)1/m(B/P)^{1/m}, 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

log⁡((B/P)1/m)−log⁡p>τ\log((B/P)^{1/m})-\log p > \tau

for a parameter τ\tau, 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 τ=1/2\tau= 1/2, chosen after a fair amount of experimentation. We did not study the choice of τ\tau systematically, and we leave it as an under-investigated question.

The bound BB is shared. Threads read log⁡B\log B without locking (a stale value is safe, just slightly wasteful), and a thread that finds a Carmichael number lowers BB under a lock.

A master thread enumerates the first four primes of PP 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 SkS_k in advance, so we run the doubling passes of Definition 3.7, except that the initial bound B0B_0 comes from a heuristic formula (see the discussion after Corollary 3.8). We take B0=2mB_0 = 2^m, where mm is the nearest integer to (klog⁡k+(0.0025k+1.024)k)/log⁡2(k \log k + (0.0025k + 1.024)k)/\log2. 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 2B′2B' examines only the n∈(B′,2B′]n \in(B', 2B'] that the previous pass did not. Within a pass, when a Carmichael number is found, we may lower BB to it. To certify SkS_k we instead run a clean pass, with BB 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 kk prime factors up to BB 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 kk and BB, so counts such as tkt_k in Table 1 are well defined and repeatable.

Results

We found SkS_k for every 40≤k≤6440 \le k \le64. 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 kk prime factors. Minimality rests on the computation. For each value we ran a clean pass (Section 4.8) with B≥SkB \ge S_k, and it found no smaller Carmichael number with kk prime factors. Our code is public, so that anyone can repeat these runs.

Pinch suggested that log⁡Sk\log S_k might be well approximated by 2log⁡2 (k−1)log⁡(k−1)2\log2\,(k-1)\log(k-1), and noted some support for this from the ratios for k≤35k \le35 [12]. Those ratios fall from 1.27 at k=10k = 10 to 0.984 at k=35k = 35, and our values continue the trend, reaching 0.940 at k=64k = 64. If β∗\beta^* is finite, then the ratio tends to 1/(2log⁡2)≈0.721/(2\log2) \approx0.72, so the two heuristics cannot both be right. The value of βk\beta_k falls from 1.23 at k=10k = 10 to 0.91 at k=35k = 35, and to 0.81 at k=64k = 64 (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 βk\beta_k grows, like 2.02+0.0025k−log⁡log⁡k2.02 + 0.0025k - \log\log k, but it stays within 3.3 bits of log⁡2Sk\log_2 S_k for 10≤k≤6410 \le k \le64.

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 SkS_k there, including every doubling pass from the heuristic starting bound.

kktime (s)kktime (s)kktime (s)
200.12261.23236.1
210.57279.03346.9
220.36285.93448.5
230.342911.535200.3
240.183013.83742.6
252.0314.738760.2
392 911.1
4444 033.6

Table 3. Time to find SkS_k on one core of a MacBook, including all doubling passes.

The times are far from monotone in kk. Most of the variation comes from where the heuristic starting bound lands relative to SkS_k, which decides how many passes are needed and how far the last pass overshoots.

The expensive computations, and every value SkS_k with 40≤k≤6440 \le k \le64, 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 kk 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 BB a little above SkS_k.

kkB/SkB/S_ktime (s)kkB/SkB/S_ktime (s)
401.051 012501.055 305
411.051 226511.054 511
421.051 284521.4055 138
431.051 378541.7780 779
451.051 8335575 297
461.052 2225630 639
471.052 2195948 064
481.052 25860111 646
491.055 31261≈400\approx400000
63712 670

Table 4. Wall-clock time of one clean pass with bound BB, on one AMD EPYC 9734 node with 112 threads.

These times, too, are not monotone in kk, for two reasons. The ratio B/SkB/S_k varies, and the work in a pass grows quickly with BB. 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 SkS_k changes slowly. It is at least 11 for every k≥15k \ge15, it is 17 for 31≤k≤5031 \le k \le50, and it is 19 for $51 \le k \le 64 ({xref}Table 2). By {xref}Proposition 3.18`, a small prime pp adds about klog⁡p−1p−2k \log\frac{p-1}{p-2} to log⁡Sk\log S_k, while it saves only the ratio of the prime it displaces, near the top of the product, to pp. The cost grows linearly in kk 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 k/log⁡log⁡kk/\log\log k.

To see how much of this is admissibility alone, we compare SkS_k with CkC_k, the least cyclic number with kk prime factors, which ignores the Korselt condition. We computed CkC_k for every k≤64k \le64 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 BB before the search starts, and at a node PP with mm primes left, the product of the next mm primes admissible to PP is a sharp lower bound for every completion. Our values agree with the terms of OEIS A264907 [19], which are listed for k≤17k \le17. Table 5 compares CkC_k with SkS_k.

kkpmin⁡(Ck)p_{\min}(C_k)pmin⁡(Sk)p_{\min}(S_k)β(Ck)\beta(C_k)βk\beta_klog⁡10(Sk/Ck)\log_{10}(S_k/C_k)
105110.8631.2311.6
157110.8451.0791.5
2011110.8311.0131.6
2511110.8040.9902.0
3011110.7880.9482.1
3511170.7670.9132.2
4011170.7520.8812.2
4511170.7490.8732.4
5011170.7380.8562.6
5311190.7310.8382.5
5419190.7270.8452.8
5519190.7240.8392.7
6019190.7070.8172.9
6419190.6960.8073.1

Table 5. The least cyclic number CkC_k and the least Carmichael number SkS_k with kk prime factors. Here β(Ck)\beta(C_k) is defined by log⁡Ck=θ(pk)+β(Ck)k\log C_k = \theta(p_k) + \beta(C_k)k.

Three things stand out. First, SkS_k is close to CkC_k: the ratio Sk/CkS_k/C_k is at most 103.110^{3.1} for k≤64k \le64. The part of βk\beta_k not explained by admissibility, βk−β(Ck)\beta_k - \beta(C_k), falls from 0.37 at k=10k = 10 to 0.11 at k=64k = 64. So at k=64k = 64, admissibility alone accounts for about 86% of βk\beta_k, and the Korselt condition for the rest. Second, the least prime factor of CkC_k jumps from 11 to 19 at k=54k = 54, skipping 13 and 17, and from then on it agrees with the least prime factor of SkS_k for every k≤64k \le64. Third, for 12≤k≤5312 \le k \le53 the least prime factor of SkS_k is at least that of CkC_k, 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 SkS_k 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, CkC_k, 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 SkS_k tends to infinity with kk, and it is o(pk)o(p_k). Moreover, it equals the least prime factor of CkC_k for all sufficiently large kk.

We note a by-product. Nielsen asked [19] whether the prime factors of CkC_k always form a normal sequence of primes, that is, whether CkC_k is obtained by choosing a first prime and then repeatedly taking the least prime admissible to all those already chosen. They do not. For k=31k=31, the cyclic number

11⋅17⋅19⋅29⋅31⋅37⋯197⋅211⋅241≈1.46⋅105911 \cdot17 \cdot19 \cdot29 \cdot31 \cdot37 \cdots197 \cdot211 \cdot241 \approx1.46 \cdot10^{59}

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 31≤k≤6431 \leq k \leq64, CkC_k 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 SkS_k. 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. [1]A. Korselt, Problème chinois, L’Intermédiaire des Mathématiciens 6 (1899), 142–143.
  2. [2]V. Šimerka, Zbytky z arithmetické polosoučtnosti, Časopis pro pěstování mathematiky a fysiky 14 (1885), 221–225.
  3. [3]R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232–238.DOI
  4. [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. [5]J. D. Swift, Table of Carmichael numbers to 10^9, Math. Comp. 29 (1975), 338–339.DOI
  6. [6]C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25 · 10^9, Math. Comp. 35 (1980), 1003–1026.
  7. [7]G. Jaeschke, Carmichael numbers to 10^12, Math. Comp. 55 (1990), 383–389.DOI
  8. [8]W. Keller, The Carmichael numbers to 10^13, Abstracts Amer. Math. Soc. 9 (1988), 328–329.
  9. [9]A. Guthmann, On the computation of Carmichael numbers, Tech. Report 218, Universität Kaiserslautern, 1992.
  10. [10]R. G. E. Pinch, The Carmichael numbers up to 10^15, Math. Comp. 61 (1993), 381–391.
  11. [11]R. G. E. Pinch, The Carmichael numbers up to 10^17, arXiv:math/0504119 (2005).DOI
  12. [12]R. G. E. Pinch, The Carmichael numbers up to 10^18, arXiv:math/0604376 (2006).DOI
  13. [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. [14]R. G. E. Pinch, Tables of Carmichael numbers, http://www.s369624816.websitehome.co.uk/rgep/cartable.html.
  15. [15]P. Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206.
  16. [16]W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703–722.DOI
  17. [17]A. Johnson, S. Webster, and J. Webster, poster, Butler MRC 2025, https://blue.butler.edu/~jwebste/MRC_2025.pdf.
  18. [18]The On-Line Encyclopedia of Integer Sequences, Sequence A006931, https://oeis.org/A006931.
  19. [19]The On-Line Encyclopedia of Integer Sequences, Sequence A264907, https://oeis.org/A264907.
  20. [20]A. Shallue and J. Webster, Algorithms for Carmichael numbers, arXiv:2506.09903 (2025).arxiv.org/abs/2506.09903
  21. [21]M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Ann. of Math. 160 (2004), 781–793.DOI
  22. [22]R. Pollack, Small values of Carmichael’s lambda function, arXiv:2606.19132 (2026).arxiv.org/abs/2606.19132
  23. [23]R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13 (1938), 242–247.DOI
  24. [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. [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. [26]A. Hildebrand and G. Tenenbaum, On the number of prime factors of an integer, Duke Math. J. 56 (1988), 471–501.DOI
  27. [27]A. Hildebrand and G. Tenenbaum, On integers free of large prime factors, Trans. Amer. Math. Soc. 296 (1986), 265–290.DOI
  28. [28]G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, 3rd ed., Graduate Studies in Mathematics 163, Amer. Math. Soc., 2015.DOI
  29. [29]G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. (2) 17 (1918), 75–115.
  30. [30]R. D. Blumofe and C. E. Leiserson, Scheduling multithreaded computations by work stealing, J. ACM 46 (1999), 720–748.
  31. [31]D. Chase and Y. Lev, Dynamic circular work-stealing deque, Proc. SPAA 2005, 21–28.DOI

Paper details

vlnc:W_fjgdbu3x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Sonnet 4.6 (bare), Claude Sonnet 5 (bare), Claude Opus 5.5

View statement
Looking for related papers…
Contents