Erdős Problem #854

Erdős Problem 854 --- collection record

PROVENANCE AND STATUS

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

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/854.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT

Let $n_k := \prod_{i=1}^k p_i$ be the $k$th primorial (product of the first $k$ primes). Let \[ 1=a_1<a_2<\cdots<a_{\varphi(n_k)}=n_k-1 \] be the increasing list of integers in $\{1,2,\dots,n_k-1\}$ that are coprime to $n_k$. Define the consecutive differences \[ g_i := a_{i+1}-a_i \qquad (1\le i\le \varphi(n_k)-1). \] The first question asks to estimate \[ m(k):=\min\{\text{even }t\ge 2: t\notin\{g_1,\dots,g_{\varphi(n_k)-1}\}\}, \] i.e. the smallest even integer not equal to any consecutive coprime gap.

The second question asks whether the set of even values attained by the $g_i$ is large, e.g. whether \[ \#\{t\in 2\mathbb{N}: t=g_i\ \text{for some }i\}\ \gg\ \max_i g_i. \]

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The statement reports computations (Lacampagne--Selfridge, as relayed by Erdős) indicating that the naive conjecture "all even $t\le \max_i g_i$ occur" fails for $n_k=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$.

ATTACK PLAN

• Structural lemmas: Relate $g_i$ to runs of consecutive integers all sharing a nontrivial gcd with $n_k$.
• Lower bounds / explicit gaps: Identify guaranteed gap values (e.g. the first gap $a_2-a_1$).
• Computation: For moderate $k$ compute the full gap-set and identify the smallest missing even and the maximum gap.

WORK

Lemma 854.1 (The first coprime after 1 is the next prime). Assume $k\ge 2$. Then $a_2=p_{k+1}$ and hence \[ g_1=a_2-a_1=p_{k+1}-1. \]

Proof. Every integer $m$ with $2\le m < p_{k+1}$ has a prime factor $q\le m < p_{k+1}$. By definition of $p_{k+1}$, every prime $q<p_{k+1}$ is among $p_1,\dots,p_k$, hence divides $n_k$. Therefore $\gcd(m,n_k)\ge q>1$, so $m$ is not coprime to $n_k$.

On the other hand, $p_{k+1}$ is prime and does not divide $n_k$ (since $n_k$ only contains the first $k$ primes), so $\gcd(p_{k+1},n_k)=1$. Thus $p_{k+1}$ is the smallest integer $>1$ coprime to $n_k$, i.e. $a_2=p_{k+1}$. Because $a_1=1$, we get $g_1=p_{k+1}-1$. $\square$

Lemma 854.2 (All gaps are even). For every $k\ge 1$ and every $i$, the difference $g_i=a_{i+1}-a_i$ is even.

Proof. Since $2\mid n_k$ for $k\ge 1$, any integer coprime to $n_k$ must be odd. Thus each $a_i$ is odd, and the difference of two odd integers is even. $\square$

Lemma 854.3 (Gaps and runs of non-coprimes). Fix $k\ge 1$ and an index $i\in\{1,\dots,\varphi(n_k)-1\}$. Let $t=g_i=a_{i+1}-a_i$. Then:

• $\gcd(a_i,n_k)=\gcd(a_{i+1},n_k)=1$;
• for every integer $j$ with $1\le j\le t-1$, we have $\gcd(a_i+j,n_k)>1$.

Conversely, if $m$ and $m+t$ are coprime to $n_k$ and every integer strictly between them has gcd $>1$ with $n_k$, then $t$ occurs as some gap $g_i$.

Proof. The forward direction is immediate from the definition of the $a_i$ as consecutive coprime integers: there are no coprime integers between $a_i$ and $a_{i+1}$.

For the converse, assume $m$ and $m+t$ are coprime to $n_k$ and all intermediate integers are not. In the increasing list of integers coprime to $n_k$, $m$ and $m+t$ appear as some consecutive entries (no other coprime lies between them), so their difference $t$ equals $g_i$ for the appropriate $i$. $\square$

Proposition 854.4 (A trivial bound on the smallest missing even). Let $G_k := \max_i g_i$ (maximum gap). Then the smallest missing even $m(k)$ satisfies \[ m(k) \le G_k+2. \] Moreover, $m(k)=G_k+2$ holds if and only if every even $t\in\{2,4,\dots,G_k\}$ occurs among the $g_i$.

Proof. Every even $t>G_k$ is absent from $\{g_i\}$ by definition of $G_k$, and the smallest even integer strictly larger than $G_k$ is $G_k+2$. Hence the smallest missing even is at most $G_k+2$.

The "if and only if" statement is just unpacking the definition of "smallest missing": if all even $\le G_k$ occur, the first missing even is $G_k+2$, whereas if some even $\le G_k$ is missing, then $m(k)\le G_k$. $\square$

FAST REALITY CHECK (explicit computations for small $k$). For each $k$ I enumerated all $a\in\{1,\dots,n_k-1\}$ with $\gcd(a,n_k)=1$, sorted them, computed $g_i=a_{i+1}-a_i$, and extracted $G_k$ and $m(k)$.

Summary (non-cyclic gaps as in the statement):

k=2: n_k=6       max gap G_k=4   smallest missing even m(k)=2
k=3: n_k=30      max gap G_k=6   smallest missing even m(k)=8
k=4: n_k=210     max gap G_k=10  smallest missing even m(k)=12
k=5: n_k=2310    max gap G_k=14  smallest missing even m(k)=16
k=6: n_k=30030   max gap G_k=22  smallest missing even m(k)=20
k=7: n_k=510510  max gap G_k=26  smallest missing even m(k)=28
k=8: n_k=9699690 max gap G_k=34  smallest missing even m(k)=32

detail for k=6 (n_k=30030):
 distinct gap values: [2,4,6,8,10,12,14,16,18,22]
 missing even values up to G_k=22: [20]
 max gap 22 occurs between consecutive coprimes 9439 and 9461.

This reproduces the reported failure of the "all even $t\le G_k$ occur" conjecture at $k=6$.

VERIFICATION

• Lemma 854.1: The key point is that if $m<p_{k+1}$ then every prime factor of $m$ is $<p_{k+1}$ and hence divides $n_k$.
• Lemma 854.3: Forward direction uses the fact that $a_i$ are consecutive among coprimes to $n_k$; converse uses the same ordering.
• Computation: For each $k\le 8$ the search is exhaustive over a finite set of size $n_k-1$. In particular, for $k=6$ the claim "20 never occurs" is verified by directly checking every one of the $\varphi(30030)-1=5759$ differences.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. (a) The first gap is always $p_{k+1}-1$ (Lemma 854.1). (b) All gaps are even (Lemma 854.2). (c) The smallest missing even satisfies $m(k)\le G_k+2$ (Proposition 854.4).
2. (ii) First gap (crisp). Determine the asymptotic size of $m(k)$ (or even of $G_k$) as $k\to\infty$, and decide whether $\#\{\text{distinct even gaps}\}\gg G_k$ holds for all large $k$.
3. (iii) Top 3 next moves.
   1. Compute $(m(k),G_k)$ for substantially larger $k$ (e.g. $k\ge 12$) and record the full set of missing even values up to $G_k$.
   2. Prove nontrivial upper/lower bounds on $G_k$ by studying the maximum length of a run of consecutive integers each divisible by some prime $\le p_k$ (a Jacobsthal-type question for $n_k$).
   3. Try to prove existence of many distinct gap sizes by constructing (via CRT) many disjoint "patterns" where two consecutive coprimes are separated by a prescribed even $t$.
4. (iv) Minimal counterexample structure. A negative answer to "many distinct gaps" would manifest as infinitely many $k$ for which the set of attained even gaps has size $o(G_k)$; concretely, many even $t\le G_k$ would be missing from $\{g_i\}$.

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 $n_k := \prod_{i=1}^k p_i$ be the $k$th primorial (product of the first $k$ primes). Let \[ 1=a_1<a_2<\cdots<a_{\varphi(n_k)}=n_k-1 \] be the increasing list of integers in $\{1,2,\dots,n_k-1\}$ that are coprime to $n_k$. Define the consecutive differences \[ g_i := a_{i+1}-a_i \qquad (1\le i\le \varphi(n_k)-1). \] The first question asks to estimate \[ m(k):=\min\{\text{even }t\ge 2: t\notin\{g_1,\dots,g_{\varphi(n_k)-1}\}\}, \] i.e. the smallest even integer not equal to any consecutive coprime gap.

The second question asks whether the set of even values attained by the $g_i$ is large, e.g. whether \[ \#\{t\in 2\mathbb{N}: t=g_i\ \text{for some }i\}\ \gg\ \max_i g_i. \]

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The statement reports computations (Lacampagne--Selfridge, as relayed by Erdős) indicating that the naive conjecture "all even $t\le \max_i g_i$ occur" fails for $n_k=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$.

ATTACK PLAN

• Structural lemmas: Relate $g_i$ to runs of consecutive integers all sharing a nontrivial gcd with $n_k$.
• Lower bounds / explicit gaps: Identify guaranteed gap values (e.g. the first gap $a_2-a_1$).
• Computation: For moderate $k$ compute the full gap-set and identify the smallest missing even and the maximum gap.

WORK

Lemma 854.1 (The first coprime after 1 is the next prime). Assume $k\ge 2$. Then $a_2=p_{k+1}$ and hence \[ g_1=a_2-a_1=p_{k+1}-1. \]

Proof. Every integer $m$ with $2\le m < p_{k+1}$ has a prime factor $q\le m < p_{k+1}$. By definition of $p_{k+1}$, every prime $q<p_{k+1}$ is among $p_1,\dots,p_k$, hence divides $n_k$. Therefore $\gcd(m,n_k)\ge q>1$, so $m$ is not coprime to $n_k$.

On the other hand, $p_{k+1}$ is prime and does not divide $n_k$ (since $n_k$ only contains the first $k$ primes), so $\gcd(p_{k+1},n_k)=1$. Thus $p_{k+1}$ is the smallest integer $>1$ coprime to $n_k$, i.e. $a_2=p_{k+1}$. Because $a_1=1$, we get $g_1=p_{k+1}-1$. $\square$

Lemma 854.2 (All gaps are even). For every $k\ge 1$ and every $i$, the difference $g_i=a_{i+1}-a_i$ is even.

Proof. Since $2\mid n_k$ for $k\ge 1$, any integer coprime to $n_k$ must be odd. Thus each $a_i$ is odd, and the difference of two odd integers is even. $\square$

Lemma 854.3 (Gaps and runs of non-coprimes). Fix $k\ge 1$ and an index $i\in\{1,\dots,\varphi(n_k)-1\}$. Let $t=g_i=a_{i+1}-a_i$. Then:

• $\gcd(a_i,n_k)=\gcd(a_{i+1},n_k)=1$;
• for every integer $j$ with $1\le j\le t-1$, we have $\gcd(a_i+j,n_k)>1$.

Conversely, if $m$ and $m+t$ are coprime to $n_k$ and every integer strictly between them has gcd $>1$ with $n_k$, then $t$ occurs as some gap $g_i$.

Proof. The forward direction is immediate from the definition of the $a_i$ as consecutive coprime integers: there are no coprime integers between $a_i$ and $a_{i+1}$.

For the converse, assume $m$ and $m+t$ are coprime to $n_k$ and all intermediate integers are not. In the increasing list of integers coprime to $n_k$, $m$ and $m+t$ appear as some consecutive entries (no other coprime lies between them), so their difference $t$ equals $g_i$ for the appropriate $i$. $\square$

Proposition 854.4 (A trivial bound on the smallest missing even). Let $G_k := \max_i g_i$ (maximum gap). Then the smallest missing even $m(k)$ satisfies \[ m(k) \le G_k+2. \] Moreover, $m(k)=G_k+2$ holds if and only if every even $t\in\{2,4,\dots,G_k\}$ occurs among the $g_i$.

Proof. Every even $t>G_k$ is absent from $\{g_i\}$ by definition of $G_k$, and the smallest even integer strictly larger than $G_k$ is $G_k+2$. Hence the smallest missing even is at most $G_k+2$.

The "if and only if" statement is just unpacking the definition of "smallest missing": if all even $\le G_k$ occur, the first missing even is $G_k+2$, whereas if some even $\le G_k$ is missing, then $m(k)\le G_k$. $\square$

FAST REALITY CHECK (explicit computations for small $k$). For each $k$ I enumerated all $a\in\{1,\dots,n_k-1\}$ with $\gcd(a,n_k)=1$, sorted them, computed $g_i=a_{i+1}-a_i$, and extracted $G_k$ and $m(k)$.

Summary (non-cyclic gaps as in the statement):

k=2: n_k=6       max gap G_k=4   smallest missing even m(k)=2
k=3: n_k=30      max gap G_k=6   smallest missing even m(k)=8
k=4: n_k=210     max gap G_k=10  smallest missing even m(k)=12
k=5: n_k=2310    max gap G_k=14  smallest missing even m(k)=16
k=6: n_k=30030   max gap G_k=22  smallest missing even m(k)=20
k=7: n_k=510510  max gap G_k=26  smallest missing even m(k)=28
k=8: n_k=9699690 max gap G_k=34  smallest missing even m(k)=32

detail for k=6 (n_k=30030):
 distinct gap values: [2,4,6,8,10,12,14,16,18,22]
 missing even values up to G_k=22: [20]
 max gap 22 occurs between consecutive coprimes 9439 and 9461.

This reproduces the reported failure of the "all even $t\le G_k$ occur" conjecture at $k=6$.

VERIFICATION

• Lemma 854.1: The key point is that if $m<p_{k+1}$ then every prime factor of $m$ is $<p_{k+1}$ and hence divides $n_k$.
• Lemma 854.3: Forward direction uses the fact that $a_i$ are consecutive among coprimes to $n_k$; converse uses the same ordering.
• Computation: For each $k\le 8$ the search is exhaustive over a finite set of size $n_k-1$. In particular, for $k=6$ the claim "20 never occurs" is verified by directly checking every one of the $\varphi(30030)-1=5759$ differences.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. (a) The first gap is always $p_{k+1}-1$ (Lemma 854.1). (b) All gaps are even (Lemma 854.2). (c) The smallest missing even satisfies $m(k)\le G_k+2$ (Proposition 854.4).
2. (ii) First gap (crisp). Determine the asymptotic size of $m(k)$ (or even of $G_k$) as $k\to\infty$, and decide whether $\#\{\text{distinct even gaps}\}\gg G_k$ holds for all large $k$.
3. (iii) Top 3 next moves.
   1. Compute $(m(k),G_k)$ for substantially larger $k$ (e.g. $k\ge 12$) and record the full set of missing even values up to $G_k$.
   2. Prove nontrivial upper/lower bounds on $G_k$ by studying the maximum length of a run of consecutive integers each divisible by some prime $\le p_k$ (a Jacobsthal-type question for $n_k$).
   3. Try to prove existence of many distinct gap sizes by constructing (via CRT) many disjoint "patterns" where two consecutive coprimes are separated by a prescribed even $t$.
4. (iv) Minimal counterexample structure. A negative answer to "many distinct gaps" would manifest as infinitely many $k$ for which the set of attained even gaps has size $o(G_k)$; concretely, many even $t\le G_k$ would be missing from $\{g_i\}$.