How long a run?
A quadratic bound for Jacobsthal’s function
Covers result 021 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
4:36. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
The nine integers 2, 3, …, 10 are each divisible by 2, 3, 5 or 7, but no ten consecutive integers are: every run of ten contains a number coprime to 210. For a number n, Jacobsthal’s j(n) is the shortest length such that every run of that length contains a number coprime to n; so j(210) = 10. Jacobsthal’s function h(k) is the largest j(n) over numbers n with at most k distinct prime factors. Equivalently, h(k) − 1 is the longest interval that one residue class for each of k primes can cover, because by the Chinese remainder theorem choosing the classes is the same as shifting the interval.
Result 021 (83 pages) claims that h(k) ≤ C·k2/(log log 3k)2 for every k ≥ 1, with an absolute constant C. In particular h(k) ≪ k2, which answers the question Jacobsthal asked and Erdős recorded in 1962: the key question of Erdős problem #970.
What it doesn’t claim
The constant C is not computed (the paper’s constants need not be effective). The true order of h(k) remains open: the best lower bound is roughly k(log k)2, far below this upper bound, and the “order of magnitude” part of problem #970 is still unanswered.
Where it stands
- Posted as a preprint
- OpenAI, dated September 25, 2026, released October 6; 83 pages
- Peer reviewed
- Not yet
- Checked in Lean
- Both bounds, by OpenAI (scope note); we have not run the check
Last checked October 19, 2026. The claim has not been withdrawn, and we found no public critique; erdosproblems.com still lists problem #970 as open. OpenAI’s Lean proofs assert both the quadratic bound and the bound with the iterated-logarithm saving; with their supporting library they run to 819 files and about 152,000 lines, not counting Mathlib. The quadratic statement is listed in OpenAI’s formalization catalog, whose review status is “unchecked”.
What was known
- Exact values: h(k) = 2, 4, 6, 10, 14, 22, 26, 34 for k = 1, …, 8. Hajdu and Saradha (2012) proved that the first k primes are a best choice for k ≤ 23, but not for k = 24, where they give 234 while h(24) = 236.
- Upper bounds: Brun’s sieve gives a fixed power of k (Erdős, 1962); Vaughan (1977) k2(log k)4; Iwaniec (1978) k2(log k)2.
- Lower bound: the construction behind the long prime gaps of Ford, Green, Konyagin, Maynard and Tao (2018) gives h(k) ≫ k(log k)2 log log log k / log log k.
How the proof goes
- A counting theorem. Forbid any residue class for every prime up to z. In an interval of length about z2/(log z)2, the paper proves that a definite number of integers survive, not just one. Taking z about k log k/log log k, that surplus absorbs the remaining prime factors.
- The decreasing-prime tree. The removed integers are sorted by the smallest prime at which they hit a forbidden class, then the same is repeated inside each piece; the result is a tree of decreasing prime tuples whose levels alternately overcount and undercount.
- The reference calculation. If every branch held exactly its expected count, the tree is governed by the classical linear-sieve functions, right at the limit where their main term vanishes; a smaller boundary term survives and is positive.
- The comparison. The actual classes can disagree with the reference. An inverse estimate shows that many disagreements force the forbidden classes to line up with one of finitely many fractions A/D (with D·ap ≡ A mod p); variance estimates narrow these fractions, and a stopping rule shows the aligned branches leave more survivors, not fewer.
The numbers in the video
- A short Python script checks the run 2–10, j(210) = 10, the values j of the first eight primorials (2, 4, 6, 10, 14, 22, 26, 34), and that h(k) equals these for k ≤ 5 by searching all sets of primes below 30.
- The growth-rate chart plots the shapes of the bounds with constants set to 1; it is not a comparison of actual values.
Read the source
- A quadratic bound for Jacobsthal’s function (PDF), dated September 25, 2026 (83 pages).
- The Lean statements: quadratic bound, iterated-log bound, and OpenAI’s scope note.
- Erdős problem #970.
- The collection’s catalog, where this is result 021.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00Covering a run
Take the primes 2, 3, 5 and 7. How long a run of consecutive integers can you find where every number is divisible by at least one of them? 2 through 10 works: 9 numbers in a row. 10 in a row is impossible. So every 10 consecutive integers contain a number with none of these four prime factors. Jacobsthal’s function, h(k), is the shortest length that always contains such a number, for any k primes and wherever the run starts. For k = 4, it’s 10. Ernst Jacobsthal studied this function from 1960, and asked whether h(k) grows at most like k². That’s the key question in Erdős problem #970, still listed as open. Result 021 in OpenAI’s math repository claims the answer is yes.
0:52The covering game
Here’s the same question as a game. For each prime, you may forbid one residue class: one out of every p integers. Your goal is to cover an interval completely. By the Chinese remainder theorem, choosing classes is the same as shifting the interval, so h(k) − 1 is the longest interval that k primes can cover. Small cases are known exactly: 2, 4, 6, 10, 14, 22, and so on. Up to 23 primes, the first k primes do best. At 24, Lajos Hajdu and N. Saradha found a set that beats them, so h(24) is 236. The construction behind the long prime gaps of Ford, Green, Konyagin, Maynard and Tao shows that h(k) grows at least roughly like k (log k)². So the truth lies somewhere between about k (log k)², and k² (log k)².
1:49Upper bounds
Upper bounds come from sieve theory. Brun’s sieve gave some fixed power of k. Robert Vaughan proved k² (log k)⁴ in 1977, and Henryk Iwaniec, in 1978, k² (log k)². Those two extra logs had stood ever since. Why does the square appear? A sieve handles primes only up to about the square root of the interval’s length. The question sits exactly at the limit of the linear sieve, the point where its usual lower bound drops to zero.
2:22The claim
The preprint, 83 pages, dated September 25, claims that h(k) is at most a constant times k²/(log log 3k)². That grows more slowly than k², and it holds for every k and every set of primes. It answers Jacobsthal’s question, and even saves a little more. The engine is a counting theorem. Forbid any class for every prime up to z. In an interval of length about z²/(log z)², not just one integer survives, but a definite number of them. That surplus absorbs the remaining prime factors. OpenAI also published a Lean proof of the quadratic bound and of the stronger version: about 800 files and 150,000 lines, not counting Mathlib. The quadratic statement is in OpenAI’s formalization catalog. We haven’t run the check.
3:18How the proof goes
First, sort the removed integers by the smallest prime at which they hit a forbidden class, then repeat inside each piece with smaller primes. This expands the count into a tree of decreasing prime tuples, whose levels alternately overcount and undercount, like inclusion and exclusion. Next, pretend every branch holds exactly its expected count. This reference tree is governed by the classical sieve functions, right at the limit where the main term vanishes. A smaller boundary term survives, and it’s positive. The real classes can disagree with the reference. The paper proves an inverse estimate: if many branches disagree, the forbidden classes must line up with one of finitely many fractions, A/D. Variance estimates narrow the fractions, and a stopping rule shows such aligned branches actually leave more survivors, not fewer.
4:12Where it stands
This is a preprint, not peer reviewed. The constant isn’t computed, and the true size of h(k) is still unknown: the gap between the lower bound and this upper bound remains wide. Four primes can cover 9 numbers in a row. If the proof holds, k primes can never cover more than a constant times k².
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.