Computational research note · Grimm's conjecture
Pick two neighbouring primes, say 23 and 29. Between them sit four composite numbers: 24, 25, 26, 27, 28. Grimm's conjecture says you can always tag every one of them with a different prime factor of its own, like 24 → 2, 25 → 5, 26 → 13, 27 → 3, 28 → 7. No two numbers share a tag, and every tag actually divides its number.
That sounds easy, composite numbers usually have several factors to pick from, but the tags have to be distinct, and a gap could in principle be too crowded for that to work out: too many numbers, not enough small primes to go around. Grimm conjectured in 1969 that this never happens, for any run of composites, however long. Nobody has found a counterexample, and Erdős and Selfridge showed that a proof would say more about how far apart primes can get than the Riemann hypothesis does. Almost sixty years later it is still open.
The way to attack it by computer is to check every gap between consecutive primes, one at a time, and exhibit a working set of tags. The last person to push that check outward was Laishram and Shorey in 2006, to about 19.2 billion. This note pushes it to a trillion (1012), fifty-two times further, in 52 minutes on four cores, and along the way builds something nobody seems to have built before: a full list of the numbers that ever actually put the tagging at risk.
Grimm's conjecture had not moved computationally since 2006. This note does five things.
Everything below is the technical version: the exact reduction to "critical members," the sieve that makes checking a trillion numbers feasible in an afternoon, the census itself, and what it does and does not prove.
Grimm's conjecture (1969) asserts that for every run of consecutive composite numbers n+1, …, n+k one can choose distinct primes p1, …, pk with pi | n+i. We verify the conjecture for all n ≤ 10¹², extending the computational record of Laishram–Shorey (2006; n ≤ 1.9236701629×10¹⁰, (secondary)) by a factor of 52. The verification is organized around the critical members of each maximal prime gap, members with no prime factor exceeding the gap length k, via the classical reduction: Grimm holds on a gap iff its critical members admit an injective assignment to primes ≤ k dividing them. We tabulate, for the first time as far as we could determine, the complete census of critical members below 10¹²: there are 18,575,022 of them, in 18,400,995 gaps, with factorizations, explicit matchings, and exact Hall margins. No margin is negative (a negative margin would be a counterexample to Grimm's conjecture). The minimum margin, 0, occurs in exactly 133 gaps below 10¹², and every one of them is tight for the same reason: it contains a prime power pa with p ≤ k (Lemma 5.1); the genuinely combinatorial way to be tight, several critical members competing for a too-small pool of primes, never occurs below 10¹². Such prime-power tight gaps occur infinitely often (Proposition 5.2); the largest below 10¹² contains 31⁸. All computations are exact integer arithmetic, cross-verified by an independent implementation on exhaustive windows and random samples, and by a further independent re-derivation performed while building this page (Section 4).
If n+1, n+2, …, n+k are all composite, there exist distinct primes p1, …, pk with pi | n+i.
Sourcing caveat, stated prominently. No primary source was readable from the sandbox that ran this research session: arXiv, OEIS, Erdős Problems, MathWorld, and the relevant journal sites were all egress-blocked, and only search-engine snippet text was reachable. Every attribution below is marked (secondary) and should be treated as unverified against the actual papers; re-verifying them is the first item in Section 7's open questions, and none has been upgraded while building this page (Section 9).
Fix consecutive primes p < q, and write k = q − p − 1 ≥ 1 for the number of composites between them; write P⁺(m) for the largest prime factor of m.
m ∈ (p, q) is critical if P⁺(m) ≤ k.
The following are equivalent: (1) every window of consecutive composites contained in (p, q) satisfies Grimm's requirement; (2) the full window p+1, …, q−1 satisfies it; (3) there is an injection φ from the critical members of (p, q) into the primes ≤ k, with φ(m) | m for every critical m.
Proof. (1)⇒(2) is trivial. (2)⇒(3): restrict a system of distinct prime representatives to the critical members; each representative divides its member, and every prime factor of a critical member is ≤ k, so the restriction is such a φ. (3)⇒(1): let W be any window inside (p, q). Assign to each critical m ∈ W the prime φ(m); to each non-critical m ∈ W any prime factor Pm > k. These choices are distinct: two non-critical members m ≠ m′ with Pm = Pm′ = P would give P | (m − m′) with 0 < |m − m′| ≤ k−1 < P, impossible; a critical and a non-critical member receive primes on opposite sides of k; the criticals are injective by hypothesis. ∎
By Hall's theorem, (3) holds iff |N(T)| ≥ |T| for every nonempty set T of critical members, where N(T) is the set of primes ≤ k dividing some member of T. Write margin(gap) = minT (|N(T)| − |T|); Grimm fails on the gap iff margin < 0. The computation below never relies on Hall's theorem to certify anything: it exhibits φ explicitly for every gap, and the margin is computed separately as an independent quantity, so a missing matching and a negative margin are two different checks that would each independently flag a counterexample.
This reduction could not be found stated together with a census of critical members anywhere reachable from the sandbox, but its substance is classical: Erdős–Selfridge already argue through Hall's theorem, and the k-smooth reduction goes back to Grimm's own paper (both (secondary)). No novelty is claimed for Lemma 2.1.
grimm_sweep.c processes all maximal gaps with left prime in [LO, HI), partitioned into four decade chunks c1–c4 covering [2, 10¹²), using four threads. Per segment of 2²² integers it runs (i) a segmented sieve of Eratosthenes (odd byte map, base primes to about 10⁶), and (ii) a cache-blocked sieve over all odd prime powers pe with p ≤ 600, accumulating res[m] = the product of pvp(m) over odd primes p ≤ 600, so that:
The walk streams each segment once. Composites that pass this smoothness test, 3,108,745,548 of them below 10¹², are factored by trial division and buffered; when the closing prime of a gap arrives and k is known, the buffered candidates with P⁺ ≤ k are that gap's critical members. This is complete for k < 600, since critical ⇒ k-smooth ⇒ 600-smooth. Gaps with k ≥ 600 would fall back to trial division up to 2000, with a hard runtime abort beyond that point, asserted, not merely assumed; neither fallback path ever triggered below 10¹², the largest gap in range having k = 539 (after 738,832,927,927). Matchings are found by augmenting paths; margins by exhaustive enumeration over subsets of a gap's critical members (the engine aborts if a gap ever exceeds 20 criticals; the largest actually observed was 10).
Everything is 64-bit exact integer arithmetic; res ≤ m < 2⁴⁰ cannot overflow. No floating point exists anywhere in the engine.
A bug worth recording, since it is the kind that is easy to ship: the first draft consulted the smooth-part array of the current segment while closing a gap, but a gap can straddle a segment boundary, where those array entries belong to the next segment and the array has already been recycled. This was caught in code review before any production run; the fix, buffering candidates as the walk streams them and deciding criticality only once the closing prime fixes k, is also structurally simpler than the original. The lesson, repeated from earlier sessions in this repository: segment-boundary state is where sieve bugs live.
Two independent implementations exist. The verifier, verify_census.py, uses sympy's isprime/factorint/nextprime and re-derives everything from scratch, sharing no code with the C engine.
The full per-gap censuses are too large to ship (Section 9), so this page could not rerun the sweep itself. Within that constraint, the following was independently redone from the committed data while building this page, in a fresh sympy 1.14 session sharing no code with either the C engine or verify_census.py:
data/tight.csv by its left prime and confirmed all 133 distinct tight gaps, and that every single one, with zero exceptions, contains at least one critical member whose factorization column lists a single prime, i.e. a genuine prime power.data/c1..c4.summary.txt), summed critical_rows in data/stats_by_decade.csv, and summed critical_rows in data/crit_by_k.csv: three independent aggregations of three different files, all agreeing on 18,575,022 members and 18,400,995 gaps.factorint, and confirmed the ten assigned primes are pairwise distinct.primepi: matches the committed data/c1.summary.txt exactly. Also computed π(10⁸) = 5,761,455 with primepi, which matches the value quoted in the note, though see Section 9 for why this one is not tied to a committed checkpoint the way π(10⁹) through π(10¹²) are.No discrepancy was found anywhere in this pass. The one thing worth flagging is not a wrong number but a traceability gap, in Section 9.
Main claim (CERTIFIED, a statement about the range computed, not beyond). For every maximal prime gap with left prime p < 10¹², the critical members admit an explicit injective assignment to primes ≤ k dividing them; consequently (Lemma 2.1), Grimm's conjecture holds for all n ≤ 10¹². No Hall margin below 10¹² is negative.
Census totals, from data/stats_by_decade.csv (decade d means 10d ≤ p < 10d+1):
| Decade | Gaps with criticals | Critical members | Max s | Tight gaps |
|---|---|---|---|---|
| ≤ 8 (p < 10⁹) | 383,963 | 409,845 | 10 | 83 |
| 9 | 1,049,580 | 1,076,022 | 6 | 15 |
| 10 | 3,761,362 | 3,807,285 | 5 | 17 |
| 11 | 13,206,090 | 13,281,870 | 4 | 18 |
| total | 18,400,995 | 18,575,022 | 10 | 133 |
s = number of critical members in a gap. The figure in "in plain terms," above, shows this same census at the finer granularity of individual decades 0 through 11; the two granularities sum to each other exactly.
data/crit_by_k.csv divided by the merged data/c*.gaphist.csv. Both axes are log scale; every point is exact measured data, and the thin connecting line is only there to help the eye, not a fit. At k=3 a critical member turns up about three times per billion gaps; by k=539, the single longest gap below 10¹², which has exactly one critical member, the rate is 1000 per 1000: every gap that long carries one. Long gaps are not just more likely to be critical, they are a different regime entirely.If a gap contains a prime power p0a (a ≥ 2) with p0 ≤ k, its margin is ≤ 0: take T = {p0a}, so N(T) = {p0}.
There are infinitely many maximal prime gaps with margin ≤ 0. Under Grimm's conjecture all margins are ≥ 0, so these gaps have margin exactly 0.
Proof. Take a ≡ 3 (mod 6), a ≥ 9, and m = 2a. Then 3 | 2a+1 (since a is odd) and 7 | 2a−1 (since 3 | a), and both neighbours exceed 7, so both are composite: the maximal gap around m has k ≥ 3 ≥ 2 = P⁺(m), so m is critical and Lemma 5.1 applies. Distinct large a give distinct gaps. ∎
The infinitude proved here is of margin-≤-0 gaps, unconditionally. That these particular gaps have margin exactly 0 rather than negative is the part that leans on Grimm's conjecture already being true; see Section 9.
Empirics from the census (CERTIFIED as data; any extrapolation beyond 10¹² is NUMERICAL):
data/tight.csv, re-grouped for this page: every single one has at least one critical member that is a pure prime power, confirmed by re-parsing every row, zero exceptions. Small bases, 2, 3, 5, 7, recur across the entire range, the low band running from p=7 to p≈5×10¹¹; the higher dots (bigger primes) only start appearing once p is large enough to hold the long local gap they need.data/multi.csv), sorted by value. Right: the ten primes they are matched to, sorted by size. Every line is an assignment the sweep actually computed, re-verified for this page by re-factoring each member with sympy. All ten primes are distinct, so this gap satisfies Grimm's requirement with room to spare: its Hall margin is 1, meaning even the gap's tightest subset of members still has one unused prime left over, which is why, despite being the busiest gap below 10¹², it is not one of the 133 tight ones.The verification is a CERTIFIED statement about n ≤ 10¹² and nothing more: evidence that no counterexample lives below the bound, not evidence for the conjecture in general. The census quantifies why verification succeeds so easily, in Laishram–Murty's smooth-number terms: critical members are vanishingly rare (18.6 million in a trillion), they concentrate in unusually long gaps and at prime powers, and Hall's condition holds with slack everywhere except at the 133 prime-power tight gaps, where the slack is exactly zero for a trivial reason. The sharp structural fact is negative: interaction tightness, the only mechanism by which Grimm's conjecture could actually fail, never once occurs below 10¹². Two k-smooth numbers whose prime supports pack into too few primes would have to sit in the same short window; that this never happens in range is consistent with, and quantifies, the heuristic that smooth numbers in short intervals are too sparse to collide, which is exactly the regime the Laishram–Murty bound g(n) = O(n0.45) lives in ((secondary); their paper could not be read during the research session).
4 cores, 15 GB RAM, gcc 13.3, Python 3.11.15, sympy 1.14. Wall times: c1 8.9 s, c2 44.7 s, c3 335.7 s, c4 2736.2 s, 52.1 minutes for the full range. Every number in this note is emitted by a committed script (grimm_sweep.c, mine_stats.py, analyze_tight.py); the full censuses (18,575,022 rows, about 940 MB) are not committed but regenerate deterministically in about 52 minutes (run_production.sh), with sha256 hashes committed in data/census_hashes.txt. Randomness appears only in verification sampling (seed 20260815). This note was produced with substantial AI assistance (Claude); AI systems are not listed as authors.
| Script | What it does | Cost | Headline output |
|---|---|---|---|
| grimm_sweep.c | 4-thread segmented sieve, cache-blocked smooth-part sieve, per-gap critical detection, Hall matching, exact margins | ≈2.8s per 10⁹ per 4 cores | census.csv, gaphist.csv, summary.txt |
| verify_census.py | Independent sympy-based verifier; exhaustive re-derivation on a window, or a light pass plus sampled heavy re-verification on a finished census | window: ≈seconds per 10⁵ integers | errors=0 |
| mine_stats.py | Streams the chunk censuses into the committed artifacts: per-decade stats, tight/multi subsets, extremes, sha256 manifest | seconds | data/*.csv |
| run_production.sh | The production sweep, decade chunks c2 through c4 | ≈50 min total | data/c*.{census,gaphist,summary} |
Everything a referee should poke first, collected in one place.
data/c*.summary.txt, so they are directly re-derivable from what is already in the repository. The other two, 86 after 155921 and 220 after 47326693, are not any chunk's overall maximum, so nothing in the committed data pins them down; the note's claim that they were reproduced rests on the research session's own live comparison against memorized values, marked (secondary). For this page, all six, including those two, were independently confirmed as genuine prime gaps of the stated size at the stated location by a fresh primality and compositeness check (Section 4). That confirms the numbers are correct; it is a different thing from confirming the sweep itself checked them at the time.data/c1..c4.summary.txt and data/post.log, and those were re-verified for this page by direct arithmetic. sympy's primepi independently confirms π(10⁸) = 5,761,455 is correct; it was just not confirmed against the sweep's own internal state.data/census_hashes.txt) and the artifacts mined from them (data/stats_by_decade.csv, data/tight.csv, data/multi.csv, data/extremes.csv, data/crit_by_k.csv). Regeneration is one committed script, about 52 minutes on 4 cores. This page's own re-verification (Section 4) worked entirely from those derived artifacts and could not re-touch the raw per-gap rows.