Erdős Problem #853

Erdős Problem 853 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/853

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/853.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/853.tex.

FORMAL RESTATEMENT

Let $p_n$ be the $n$th prime and $d_n=p_{n+1}-p_n$ as above. For an integer $x\ge 1$, define \[ r(x):= \min\left\{ t\in 2\mathbb{N}:\ \forall n\in\{1,\dots,x\},\ d_n\ne t\right\}. \] (So $r(x)$ is the smallest even positive integer which does not occur among the first $x$ prime gaps.)

The problem asks whether $r(x)\to\infty$ as $x\to\infty$, and even whether $r(x)/\log x\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The evenness restriction is necessary because $d_n$ is even for $n\ge 2$.

ATTACK PLAN

• Proof-track: Derive structural constraints on which even gaps can appear among consecutive primes (this connects to conjectures like Polignac's).
• Disproof-track: Search for an even $t$ that plausibly never appears as a consecutive prime gap (no such $t$ is known to me from the given text), or for computational evidence that $r(x)$ stabilizes.
• Reality-check: Compute $r(x)$ for moderate $x$ and compare to $\log x$.

WORK

Lemma 853.1 (Even gaps past $p_2$). For every $n\ge 2$, $d_n$ is even.

Proof. This is Lemma 852.1. $\square$

Lemma 853.2 (Monotonicity). The function $r(x)$ is nondecreasing in $x$.

Proof. If $x_1\le x_2$, then the set of gaps seen up to index $x_1$, namely $\{d_n:1\le n\le x_1\}$, is a subset of the gaps seen up to $x_2$. Therefore the set of even integers missing up to $x_2$ is a subset of those missing up to $x_1$, so the smallest missing even integer cannot decrease: $r(x_2)\ge r(x_1)$. $\square$

Lemma 853.3 (A pigeonhole upper bound $r(x)\le 2x$). For every integer $x\ge 1$, $r(x)\le 2x$.

Proof. Consider the $x$ even integers $2,4,6,\dots,2x$. If every one of these occurred among $d_1,\dots,d_x$, then in particular at least $x$ of the gaps $d_1,\dots,d_x$ would be even.

But $d_1=p_2-p_1=3-2=1$ is odd, so among $d_1,\dots,d_x$ there are at most $x-1$ even values. Hence it is impossible for all $x$ even integers $2,4,\dots,2x$ to appear among the first $x$ gaps. Therefore at least one even integer $\le 2x$ is missing, and by definition $r(x)$ (the smallest missing even) satisfies $r(x)\le 2x$. $\square$

Lemma 853.4 (Trivial bound via the maximum observed even gap). Let $M(x):=\max\{d_n:1\le n\le x\ \text{and}\ d_n\ \text{even}\}$ (for $x\ge 2$). Then $r(x)\le M(x)+2$.

Proof. Every even integer $t>M(x)$ is absent from $\{d_1,\dots,d_x\}$ by definition of $M(x)$. The smallest even integer strictly larger than $M(x)$ is $M(x)+2$, so the smallest missing even integer is at most $M(x)+2$. $\square$

FAST REALITY CHECK (computed values). Using primes up to index $x=10^6$ (so about $p_{10^6}\approx 1.5\times 10^7$), I computed the set of even gaps occurring among $d_1,\dots,d_x$ and extracted $r(x)$.

Results:

Selected x and r(x):
 r(10)=8
 r(20)=8
 r(50)=16
 r(100)=16
 r(200)=16
 r(500)=30
 r(1,000)=36
 r(2,000)=38
 r(5,000)=46
 r(10,000)=66
 r(20,000)=74
 r(50,000)=92
 r(100,000)=102
 r(200,000)=116
 r(500,000)=140
 r(1,000,000)=156

For x=1,000,000:
 max even gap among d_1..d_x is 154
 distinct even gaps seen: 77 values, min=2, max=154
 all even gaps 2,4,...,154 occur at least once; the first missing even is 156.

VERIFICATION

• Definition check: $r(x)$ ignores odd gaps by definition (searches over $t\in 2\mathbb{N}$).
• Lemma 853.3: The only place the special gap $d_1=1$ is used is to ensure at most $x-1$ even gaps among the first $x$ gaps.
• Computation sanity: For $x=1$, the gap multiset is $\{1\}$, so the smallest missing even is $2$, hence $r(1)=2$, consistent with monotonicity and the reported larger values.
• Computed claim "all evens up to 154 appear": This was verified by explicitly checking membership of each even $\le 154$ in the computed set of gaps.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. $r(x)$ is nondecreasing (Lemma 853.2) and satisfies the unconditional bounds $r(x)\le 2x$ (Lemma 853.3) and $r(x)\le M(x)+2$ where $M(x)$ is the maximum even gap seen up to $x$ (Lemma 853.4).
2. (ii) First gap (crisp). Prove or disprove: for every fixed even $t$, there exists $n$ with $d_n=t$ (equivalently, $r(x)\to\infty$).
3. (iii) Top 3 next moves.
   1. Try to show that for each fixed even $t$, the pattern "two primes at distance $t$ with all in-between composites" occurs at least once (a very weak form of Polignac-type statements).
   2. Compute $r(x)$ for much larger $x$ and record when each even gap $2m$ first appears; look for systematic obstructions/modular patterns.
   3. Prove nontrivial lower bounds on $r(x)$ (e.g. $r(x)\gg \log x$) by showing that among the first $x$ gaps, not all small even values can be covered.
4. (iv) Minimal counterexample structure. If $r(x)$ fails to go to infinity, then there exists an even $t_0$ such that $d_n\ne t_0$ for all $n$ (i.e. a specific even integer never occurs as a consecutive prime gap).

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Let $p_n$ be the $n$th prime and $d_n=p_{n+1}-p_n$ as above. For an integer $x\ge 1$, define \[ r(x):= \min\left\{ t\in 2\mathbb{N}:\ \forall n\in\{1,\dots,x\},\ d_n\ne t\right\}. \] (So $r(x)$ is the smallest even positive integer which does not occur among the first $x$ prime gaps.)

The problem asks whether $r(x)\to\infty$ as $x\to\infty$, and even whether $r(x)/\log x\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The evenness restriction is necessary because $d_n$ is even for $n\ge 2$.

ATTACK PLAN

• Proof-track: Derive structural constraints on which even gaps can appear among consecutive primes (this connects to conjectures like Polignac's).
• Disproof-track: Search for an even $t$ that plausibly never appears as a consecutive prime gap (no such $t$ is known to me from the given text), or for computational evidence that $r(x)$ stabilizes.
• Reality-check: Compute $r(x)$ for moderate $x$ and compare to $\log x$.

WORK

Lemma 853.1 (Even gaps past $p_2$). For every $n\ge 2$, $d_n$ is even.

Proof. This is Lemma 852.1. $\square$

Lemma 853.2 (Monotonicity). The function $r(x)$ is nondecreasing in $x$.

Proof. If $x_1\le x_2$, then the set of gaps seen up to index $x_1$, namely $\{d_n:1\le n\le x_1\}$, is a subset of the gaps seen up to $x_2$. Therefore the set of even integers missing up to $x_2$ is a subset of those missing up to $x_1$, so the smallest missing even integer cannot decrease: $r(x_2)\ge r(x_1)$. $\square$

Lemma 853.3 (A pigeonhole upper bound $r(x)\le 2x$). For every integer $x\ge 1$, $r(x)\le 2x$.

Proof. Consider the $x$ even integers $2,4,6,\dots,2x$. If every one of these occurred among $d_1,\dots,d_x$, then in particular at least $x$ of the gaps $d_1,\dots,d_x$ would be even.

But $d_1=p_2-p_1=3-2=1$ is odd, so among $d_1,\dots,d_x$ there are at most $x-1$ even values. Hence it is impossible for all $x$ even integers $2,4,\dots,2x$ to appear among the first $x$ gaps. Therefore at least one even integer $\le 2x$ is missing, and by definition $r(x)$ (the smallest missing even) satisfies $r(x)\le 2x$. $\square$

Lemma 853.4 (Trivial bound via the maximum observed even gap). Let $M(x):=\max\{d_n:1\le n\le x\ \text{and}\ d_n\ \text{even}\}$ (for $x\ge 2$). Then $r(x)\le M(x)+2$.

Proof. Every even integer $t>M(x)$ is absent from $\{d_1,\dots,d_x\}$ by definition of $M(x)$. The smallest even integer strictly larger than $M(x)$ is $M(x)+2$, so the smallest missing even integer is at most $M(x)+2$. $\square$

FAST REALITY CHECK (computed values). Using primes up to index $x=10^6$ (so about $p_{10^6}\approx 1.5\times 10^7$), I computed the set of even gaps occurring among $d_1,\dots,d_x$ and extracted $r(x)$.

Results:

Selected x and r(x):
 r(10)=8
 r(20)=8
 r(50)=16
 r(100)=16
 r(200)=16
 r(500)=30
 r(1,000)=36
 r(2,000)=38
 r(5,000)=46
 r(10,000)=66
 r(20,000)=74
 r(50,000)=92
 r(100,000)=102
 r(200,000)=116
 r(500,000)=140
 r(1,000,000)=156

For x=1,000,000:
 max even gap among d_1..d_x is 154
 distinct even gaps seen: 77 values, min=2, max=154
 all even gaps 2,4,...,154 occur at least once; the first missing even is 156.

VERIFICATION

• Definition check: $r(x)$ ignores odd gaps by definition (searches over $t\in 2\mathbb{N}$).
• Lemma 853.3: The only place the special gap $d_1=1$ is used is to ensure at most $x-1$ even gaps among the first $x$ gaps.
• Computation sanity: For $x=1$, the gap multiset is $\{1\}$, so the smallest missing even is $2$, hence $r(1)=2$, consistent with monotonicity and the reported larger values.
• Computed claim "all evens up to 154 appear": This was verified by explicitly checking membership of each even $\le 154$ in the computed set of gaps.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. $r(x)$ is nondecreasing (Lemma 853.2) and satisfies the unconditional bounds $r(x)\le 2x$ (Lemma 853.3) and $r(x)\le M(x)+2$ where $M(x)$ is the maximum even gap seen up to $x$ (Lemma 853.4).
2. (ii) First gap (crisp). Prove or disprove: for every fixed even $t$, there exists $n$ with $d_n=t$ (equivalently, $r(x)\to\infty$).
3. (iii) Top 3 next moves.
   1. Try to show that for each fixed even $t$, the pattern "two primes at distance $t$ with all in-between composites" occurs at least once (a very weak form of Polignac-type statements).
   2. Compute $r(x)$ for much larger $x$ and record when each even gap $2m$ first appears; look for systematic obstructions/modular patterns.
   3. Prove nontrivial lower bounds on $r(x)$ (e.g. $r(x)\gg \log x$) by showing that among the first $x$ gaps, not all small even values can be covered.
4. (iv) Minimal counterexample structure. If $r(x)$ fails to go to infinity, then there exists an even $t_0$ such that $d_n\ne t_0$ for all $n$ (i.e. a specific even integer never occurs as a consecutive prime gap).