Erdős problem #853 — live audit, exact reductions, and certified finite progress

Date: 2026-07-27 UTC

Claim labels used throughout:

• (a) elementary-rigorous — a complete proof is given here.
• (b) rigorous-modulo-named-theorem — the deduction is rigorous from the named published theorem.
• (c) plausible/structural-unverified — heuristic or conjectural only.
• (d) computational-only — a finite computation, with the precise verification status stated.

0. Mandatory live-page audit

The Cloudflare-protected live page and its discussion thread were read through the

Bright Data browser path on 2026-07-27, before doing any mathematics:

• live problem
• live discussion
• live LaTeX view

Verbatim current statement

> Let \(d_n=p_{n+1}-p_n\), where \(p_n\) is the \(n\)th prime. Let \(r(x)\) be the smallest even integer \(t\) such that \(d_n=t\) has no solutions for \(n\leq x\).

>

> Is it true that \(r(x)\to \infty\)? Or even \(r(x)/\log x \to\infty\)?

The page is marked OPEN. It says that Erdős omitted the condition that \(t\)

be even in the original source, but that this condition is necessary. It lists

the related sequences A001223 and A390769 and says “Formalised statement? Yes.”

This is a formalisation of the statement, not a proof.

The mandatory collision gate passed:

| live field | value |

|---|---|

| Claimed proofs | 0 |

| Currently working on this problem | None |

| Interested in collaborating | None |

| Likes this problem | hediibl |

| This problem looks difficult | ebarschkis, hediibl |

| This problem looks tractable | None |

| Results could be formalisable | None |

| Working on formalising results | None |

The three live comments are:

1. Dogmachine, 2025-08-09: “Would imply every that every even number is a

prime gap, which is unknown.”

2. Giorgos Kalogeropoulos, 2025-11-18: “I submitted \(r(x)\) as A390769.

Draft edits are here” (the page says it was updated in response).

3. Adenwalla, 2026-03-19: “*Every sufficiently large even number is a prime

gap, I believe”.

None is a proof claim or a current-worker declaration. Strictly, the first

limit would imply that every positive even integer is a prime gap; the word

“sufficiently” becomes harmless only because any fixed finite initial range can

be checked separately.

1. Exact reformulation of both questions

For \(m\geq1\), define

and put \(C_0=0\). Thus \(C_m\) is the first index by which every even gap

\(2,4,\ldots,2m\) has appeared.

Exact identity

For every integer \(x\geq0\),

Proof (a). The inequality \(r(x)>2m\) says exactly that none of

\(2,4,\ldots,2m\) is missing among \(d_1,\ldots,d_x\). This is equivalent to

\(F_j\leq x\) for every \(j\leq m\), hence to \(C_m\leq x\). Taking the largest

such \(m\) gives (1).

Two exact equivalences follow.

In words, the first question is precisely whether the prime-gap sequence is

surjective onto the positive even integers. It asks for one occurrence of each

gap, not infinitely many. (a)

Assuming all \(F_m\) are finite,

Proof (a). First note \(C_m\geq m\), since \(m\) distinct gap values need

at least \(m\) indices, so \(C_m\to\infty\). If the left side of (3) holds, put

\(x=C_m-1\). Some gap at most \(2m\) is still missing, so

\(r(x)\leq2m\). Hence

which gives \(\log C_m=o(m)\). Conversely, for an arbitrary large \(x\), let

\(M=\max\{m:C_m\leq x\}\). Then \(x \[ \frac{r(x)}{\log x} =\frac{2(M+1)}{\log x} \geq\frac{2(M+1)}{\log C_{M+1}}\to\infty. \]

By the prime number theorem, (3) is equivalently a subexponential bound for

the largest first-occurrence prime among gaps through \(2m\). **(b), using

the prime number theorem.**

This is the cleanest isolation of what the second question needs: fixed-gap

existence is not enough; the simultaneous completion time must be

subexponential in the gap parameter.

2. Explicit certified witnesses for every even gap through 1572

The current Prime Gap List is a community-curated continuation of Thomas

Nicely's tables. Its first-occurrence table

currently has an entry for every even gap through \(1572\), with \(1574\) the

first absent size. Its exhaustive-analysis page

reports that the scan frontier reached \(10^{20}\) on 2026-05-08. The exact

seed data used here is

commit 1b5a4749a0660d621b84007b37083885cf02cca4.

The full upstream CSV has SHA-256

a0e1879ce924d3ce45e2dc5e69980e0fa36cf92b1a2f345a11094d4a916b8e6f.

I did not trust the table's primality or consecutiveness flags. The

standalone checker embeds the 786 endpoint pairs and re-proves from scratch

that each is a consecutive-prime gap.

Checker logic

For each candidate \((p,p+g)\):

1. It factors \(p-1\) and \(p+g-1\) using deterministic-seed Pollard–Brent rho.

2. It recursively certifies every prime factor and both endpoints with Lucas

certificates. If \(n-1=\prod q_i^{e_i}\), the checker finds \(a\) satisfying

\[ a^{n-1}\equiv1\pmod n,\qquad \gcd(a^{(n-1)/q_i}-1,n)=1\quad\text{for every }q_i. \]

This proves \(n\) prime: for every prime \(\ell\mid n\), the order of \(a\)

modulo \(\ell\) is divisible by \(q_i^{e_i}\) for every \(i\), hence is

exactly \(n-1\). Therefore \(n-1\mid\ell-1\); since \(\ell\leq n\),

necessarily \(\ell=n\). (a)

3. Every even interior integer gets divisor \(2\). Every odd interior integer

gets either an explicit small divisor or a failing strong Miller–Rabin base.

Failure of a strong probable-prime test is a one-way, exact compositeness

proof; the checker never treats passing such a test as a primality proof.

(a)

The successful run certified:

| item | independently checked value |

|---|---:|

| even gap sizes | 786 (every even \(2\leq g\leq1572\)) |

| endpoint primes | 1,572 |

| recursive Lucas-certified prime nodes | 5,763 |

| largest Lucas base needed | 43 |

| even interior composites (factor 2) | 309,291 |

| odd interior composites (small factor) | 237,726 |

| odd interior composites (strong-MR failure) | 70,779 |

| total interior composites | 617,796 |

| embedded witness-data SHA-256 | 26475aba50a67843e2ba6cf382fcbeaafb2eec77b0d395752b804cbb67c22c64 |

These are exact finite computations. **(d), with the correctness of every

accepted certificate justified by (a).**

The last six witnesses are:

| gap \(g\) | certified left endpoint \(p\) |

|---:|---:|

| 1562 | 51,330,518,963,552,306,591 |

| 1564 | 50,141,184,398,287,532,959 |

| 1566 | 47,526,443,055,735,575,447 |

| 1568 | 33,020,270,934,358,330,391 |

| 1570 | 92,489,057,256,472,962,493 |

| 1572 | 18,571,673,432,051,830,099 |

Let

If a witness starts at \(p=p_n\), then trivially \(n\leq p\leq X\).

Consequently every even gap through 1572 occurs among \(d_n\) for \(n\leq X\),

and therefore

This is a certified finite lower bound, not an asymptotic result. **(d), with

the deduction from the certificates elementary-rigorous (a).**

In light of these certificates, (2) reduces further to the exact remaining

statement:

> Every even \(g\geq1574\) occurs at least once as a consecutive-prime gap.

The first concrete unresolved size in the current project data is \(1574\).

The project's claim that no such gap starts below \(10^{20}\) depends on its

large external exhaustive scan and was not independently re-sieved here.

It is therefore only an externally reported computational fact, (d), and

is not used in (4).

3. Exact independent computation through \(10^9\)

The same standalone script independently constructs an odd-only Eratosthenes

sieve through \(10^9\), enumerates the primes in increasing order, and records

the first index of every observed gap. No endpoint list or OEIS term is used

in this part.

The run found

It therefore enumerated exactly \(d_1,\ldots,d_{50\,847\,533}\). Every even

gap \(2,\ldots,252\) occurs in that prefix, while \(254\) does not. Thus

The computation took 45.5 wall-clock seconds including the certificate phase

and peaked at 835,444 KiB resident memory. The sieve phase itself took 43.3

seconds. (d), exact exhaustive computation; sieve correctness is (a).

Here is the complete prefix-completion breakpoint table. “Completed record

gap” is the gap whose first occurrence raises \(C_m\); “new \(r\)” is the

smallest missing even gap immediately after that occurrence.

| completed record gap | first index | endpoint pair | new \(r\) |

|---:|---:|---:|---:|

| 2 | 2 | (3, 5) | 4 |

| 4 | 4 | (7, 11) | 6 |

| 6 | 9 | (23, 29) | 8 |

| 8 | 24 | (89, 97) | 10 |

| 10 | 34 | (139, 149) | 12 |

| 12 | 46 | (199, 211) | 16 |

| 16 | 282 | (1,831, 1,847) | 26 |

| 26 | 367 | (2,477, 2,503) | 28 |

| 28 | 429 | (2,971, 2,999) | 30 |

| 30 | 590 | (4,297, 4,327) | 32 |

| 32 | 738 | (5,591, 5,623) | 36 |

| 36 | 1,183 | (9,551, 9,587) | 38 |

| 38 | 3,302 | (30,593, 30,631) | 46 |

| 46 | 7,970 | (81,463, 81,509) | 56 |

| 56 | 8,028 | (82,073, 82,129) | 64 |

| 64 | 8,688 | (89,689, 89,753) | 66 |

| 66 | 14,862 | (162,143, 162,209) | 70 |

| 70 | 15,783 | (173,359, 173,429) | 74 |

| 74 | 34,202 | (404,597, 404,671) | 80 |

| 80 | 44,773 | (542,603, 542,683) | 88 |

| 88 | 44,903 | (544,279, 544,367) | 92 |

| 92 | 73,321 | (927,869, 927,961) | 94 |

| 94 | 85,787 | (1,100,977, 1,101,071) | 102 |

| 102 | 110,224 | (1,444,309, 1,444,411) | 108 |

| 108 | 165,326 | (2,238,823, 2,238,931) | 116 |

| 116 | 402,884 | (5,845,193, 5,845,309) | 124 |

| 124 | 460,883 | (6,752,623, 6,752,747) | 134 |

| 134 | 474,029 | (6,958,667, 6,958,801) | 140 |

| 140 | 515,910 | (7,621,259, 7,621,399) | 142 |

| 142 | 685,903 | (10,343,761, 10,343,903) | 144 |

| 144 | 786,922 | (11,981,443, 11,981,587) | 150 |

| 150 | 887,313 | (13,626,257, 13,626,407) | 156 |

| 156 | 1,150,400 | (17,983,717, 17,983,873) | 158 |

| 158 | 2,959,782 | (49,269,581, 49,269,739) | 166 |

| 166 | 4,875,380 | (83,751,121, 83,751,287) | 186 |

| 186 | 8,321,465 | (147,684,137, 147,684,323) | 194 |

| 194 | 9,330,121 | (166,726,367, 166,726,561) | 200 |

| 200 | 20,226,285 | (378,043,979, 378,044,179) | 224 |

| 224 | 21,833,975 | (409,866,323, 409,866,547) | 226 |

| 226 | 27,335,370 | (519,653,371, 519,653,597) | 228 |

| 228 | 45,808,557 | (895,858,039, 895,858,267) | 254 |

The canonical serialization of these 41 rows has SHA-256

805bfab1f60cebcd6bdb2fdeaf4f634bbe76abb75cb2d379274fcfd60552105e.

In particular, the sieve proves the slightly stronger interval statement

\(r(x)=254\) for every

\(45\,808\,557\leq x\leq50\,847\,533\). (d)

4. What the primary literature actually gives

Original source

The original item is P. Erdős, “On some of my problems in number theory I

would most like to see solved,” Number Theory (Ootacamund, 1984), Lecture

Notes in Mathematics 1122 (1985), 74–84,

DOI 10.1007/BFb0075752.

The author-archive scan, p. 80,

contains the \(r(x)\) question and says that even \(r(x)\to\infty\) could not

be attacked by the methods then available. The scan confirms that the original

wording omitted “even,” exactly as the live page notes.

Known unconditional theory: many values, not every value

Pintz defines a Polignac number as an even \(h\) for which \(d_n=h\)

infinitely often. In

arXiv:1305.6289, §§2.2 and 4, he proves:

• the Polignac numbers have positive lower asymptotic density; and
• there is an ineffective constant \(C\) such that every interval

\([M,M+C]\) contains a Polignac number.

These are rigorous published results from the Zhang/GPY machinery. **(b),

using Pintz's theorems.** They show that an infinite, even syndetic, set of

gap sizes occurs infinitely often. They do not control a prescribed even

integer. A syndetic set can omit \(1574\), or any other fixed value, forever,

so these theorems do not imply (2).

The Polymath8 paper

arXiv:1407.4897 proves

\(H_1\leq246\), hence at least one even gap at most 246 occurs infinitely

often. (b) Again, it neither identifies all prescribed gaps nor supplies

the uniform completion bound in (3).

Computation in the literature

Oliveira e Silva, Herzog, and Pardi,

[“Empirical verification ... and computation of prime gaps up to

\(4\cdot10^{18}\)”](https://www.ams.org/mcom/2014-83-288/S0025-5718-2013-02787-1/S0025-5718-2013-02787-1.pdf),

Math. Comp. 83 (2014), 2033–2060, DOI

10.1090/S0025-5718-2013-02787-1, describe an exhaustive segmented sieve,

gap counts, and first occurrences through \(4\cdot10^{18}\). Their computation

took about 770 one-core CPU years; the full range through

\(3\cdot10^{17}\), all intervals containing one of the first 100 relevant

occurrences, and about 4% of the remaining intervals were double-checked.

These are the paper's reported computational safeguards, not a theorem about

all future gap sizes. (d)

OEIS A390769 is exactly the sequence \(r(n)\), but

currently publishes only its initial 72 values. The table in §3 above extends

the independently recomputed exact indexed data far beyond those displayed

terms.

Heuristic scale

Kourbatov and Wolf,

arXiv:2002.02115, published in the

Journal of Integer Sequences 23 (2020), Article 20.9.3, heuristically expect

a first-occurrence endpoint on the scale

for ordinary primes (\(q=1\) in their arithmetic-progression notation).

If such a bound held uniformly for every even \(d\leq2m\), it would give

\(\log C_m=O(\sqrt m)\) and settle the stronger question. It is explicitly a

heuristic supported by computation, not a uniform theorem. (c)

Searches by the exact \(r(x)\) phrasing, by surjectivity of the prime-gap

sequence, and through the cited first-occurrence/Polignac literature found no

primary source proving either limit. No arXiv identifier or paper cited above

was accepted without opening its actual abstract or full text.

5. A clean conditional construction and the exact missing lemma

For any fixed even \(h\), choose distinct primes \(q_j>h\) for

\(1\leq j

theorem to choose

python runs/erdos853_wave6o_verify.py

ALL REQUESTED CHECKS PASSED

python runs/erdos853_wave6o_verify.py --certificate-only