Erdős Problem #680

Erdős Problem 680 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT. Let $p(m)$ denote the least prime divisor of $m$ (with $p(1)$ undefined and $p(m)=m$ if $m$ is prime). Is it true that for all sufficiently large integers $n$ there exists an integer $k\ge1$ such that \[ p(n+k)\;>\;k^{2}+1\ ? \] A further question in the statement asks whether one can prove the statement is false if $k^{2}+1$ is replaced by $e^{(1+\varepsilon)\sqrt{k}}+C_{\varepsilon}$ for every $\varepsilon>0$.

QUICK LITERATURE/CONTEXT CHECK. The problem text notes that the "$e^{(1+\varepsilon)\sqrt{k}}$" variant would follow from certain plausible assumptions, and asks for an unconditional resolution. I do not assume any additional external results.

ATTACK PLAN. Two immediate observations are: $1$ The inequality forces $n+k>k^{2}+1$, hence $k$ cannot be much larger than $\sqrt n$. $2$ If $n+k$ is composite then $p(n+k)\le\sqrt{n+k}$, so when $k^{2}$ exceeds $\sqrt{n+k}$ the only way the inequality can hold is if $n+k$ is prime. The problem therefore blends existence of "$k^{2}$-rough" integers in short intervals with prime gaps.

WORK. Lemma 1 (All even $n$ work with $k=1$). If $n$ is even and $n\ge 2$, then the choice $k=1$ satisfies $p(n+1)>1^{2}+1$.

Proof. If $n$ is even then $n+1$ is odd. For $n\ge2$, we have $n+1\ge3$, so its least prime factor is at least $3$. Thus \[p(n+1)\ge 3>2=1^{2}+1. \] So $k=1$ works for every even $n\ge2$. $\square$

Lemma 2 (A necessary size bound on $k$). If $p(n+k)>k^{2}+1$ holds, then necessarily \[n+k>k^{2}+1,\quad\text{equivalently }\quad k^{2}-k+1<n. \] In particular, \[k\le \left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor. \]

Proof. Always $p(n+k)\le n+k$ (since the least prime factor is at most the number itself). Hence $p(n+k)>k^{2}+1$ forces $n+k\ge p(n+k)>k^{2}+1$. Rearranging gives $k^{2}-k+1<n$. Solving the quadratic inequality $k^{2}-k+(1-n)<0$ yields $k<(1+\sqrt{4n-3})/2$, hence the stated integer bound. $\square$

Lemma 3 (When $k$ is large, $n+k$ must be prime). If $m$ is composite then $p(m)\le \sqrt m$. Consequently, if $p(n+k)>k^{2}+1$ and $k^{2}\ge \sqrt{n+k}$, then $n+k$ must be prime.

Proof. If $m$ is composite, write $m=ab$ with $1<a\le b<m$. Then $a\le \sqrt m$. The least prime divisor satisfies $p(m)\le a\le \sqrt m$. Apply this with $m=n+k$. If $n+k$ were composite, then $p(n+k)\le\sqrt{n+k}\le k^{2}$, contradicting $p(n+k)>k^{2}+1$. $\square$

VERIFICATION (FAST REALITY CHECK). Because of Lemma 2, for each fixed $n$ there are only finitely many $k$ to check (indeed $k\ll\sqrt n$). I exhaustively searched all $n\le 200\,000$ and all admissible $k$ (i.e. those with $n+k>k^{2}+1$) and found:

Exceptions (no k exists) for n<=200000:  [3, 7, 13, 23, 31, 113, 115]
For all other 2<=n<=200000, at least one k exists.
Maximum of the minimal such k in this range: 74 (attained at n=155933).

This is strong computational evidence that the statement might be true for all $n\ge 117$ (or perhaps all $n$ except the listed finite set), but it is not a proof.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. Every even $n\ge2$ has a solution (take $k=1$). For any $n$, any solution $k$ must satisfy $k^{2}-k+1<n$ (Lemma 2); and if $k^{2}\ge\sqrt{n+k}$ then a solution forces $n+k$ to be prime (Lemma 3).

(ii) First gap (crisp). For odd $n$, one needs an unconditional argument guaranteeing the existence of some $k\le (1+\sqrt{4n-3})/2$ with $n+k$ either prime or composite but with all prime factors $>k^{2}+1$. I do not have a method to force such a "$k^{2}$-rough" value in the short interval $[n+1,\,n+O(\sqrt n)]$.

(iii) Top 3 next moves. $1$ Try to prove a "rough numbers in short intervals" lemma tailored to the moving threshold $k^{2}$: show that among $n+1,\dots,n+\lfloor c\sqrt n\rfloor$ there is some $m=n+k$ with least prime factor $>k^{2}$. $2$ Investigate whether existing (unconditional) bounds on prime gaps in intervals of length $\asymp \sqrt n$ would imply the statement via Lemma 3. $3$ Extend computation much further (e.g. $n\le 10^{7}$) and record the distribution of the minimal witnessing $k$ for odd $n$; this may suggest a constructive pattern.

(iv) Minimal counterexample structure. A counterexample $n$ must be odd (since even $n$ work with $k=1$). It would require that for every admissible $k$ with $n+k>k^{2}+1$, the integer $n+k$ has a prime factor at most $k^{2}+1$.

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(m)$ denote the least prime divisor of $m$ (with $p(1)$ undefined and $p(m)=m$ if $m$ is prime). Is it true that for all sufficiently large integers $n$ there exists an integer $k\ge1$ such that \[ p(n+k)\;>\;k^{2}+1\ ? \] A further question in the statement asks whether one can prove the statement is false if $k^{2}+1$ is replaced by $e^{(1+\varepsilon)\sqrt{k}}+C_{\varepsilon}$ for every $\varepsilon>0$.

QUICK LITERATURE/CONTEXT CHECK. The problem text notes that the "$e^{(1+\varepsilon)\sqrt{k}}$" variant would follow from certain plausible assumptions, and asks for an unconditional resolution. I do not assume any additional external results.

ATTACK PLAN. Two immediate observations are: $1$ The inequality forces $n+k>k^{2}+1$, hence $k$ cannot be much larger than $\sqrt n$. $2$ If $n+k$ is composite then $p(n+k)\le\sqrt{n+k}$, so when $k^{2}$ exceeds $\sqrt{n+k}$ the only way the inequality can hold is if $n+k$ is prime. The problem therefore blends existence of "$k^{2}$-rough" integers in short intervals with prime gaps.

WORK. Lemma 1 (All even $n$ work with $k=1$). If $n$ is even and $n\ge 2$, then the choice $k=1$ satisfies $p(n+1)>1^{2}+1$.

Proof. If $n$ is even then $n+1$ is odd. For $n\ge2$, we have $n+1\ge3$, so its least prime factor is at least $3$. Thus \[p(n+1)\ge 3>2=1^{2}+1. \] So $k=1$ works for every even $n\ge2$. $\square$

Lemma 2 (A necessary size bound on $k$). If $p(n+k)>k^{2}+1$ holds, then necessarily \[n+k>k^{2}+1,\quad\text{equivalently }\quad k^{2}-k+1<n. \] In particular, \[k\le \left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor. \]

Proof. Always $p(n+k)\le n+k$ (since the least prime factor is at most the number itself). Hence $p(n+k)>k^{2}+1$ forces $n+k\ge p(n+k)>k^{2}+1$. Rearranging gives $k^{2}-k+1<n$. Solving the quadratic inequality $k^{2}-k+(1-n)<0$ yields $k<(1+\sqrt{4n-3})/2$, hence the stated integer bound. $\square$

Lemma 3 (When $k$ is large, $n+k$ must be prime). If $m$ is composite then $p(m)\le \sqrt m$. Consequently, if $p(n+k)>k^{2}+1$ and $k^{2}\ge \sqrt{n+k}$, then $n+k$ must be prime.

Proof. If $m$ is composite, write $m=ab$ with $1<a\le b<m$. Then $a\le \sqrt m$. The least prime divisor satisfies $p(m)\le a\le \sqrt m$. Apply this with $m=n+k$. If $n+k$ were composite, then $p(n+k)\le\sqrt{n+k}\le k^{2}$, contradicting $p(n+k)>k^{2}+1$. $\square$

VERIFICATION (FAST REALITY CHECK). Because of Lemma 2, for each fixed $n$ there are only finitely many $k$ to check (indeed $k\ll\sqrt n$). I exhaustively searched all $n\le 200\,000$ and all admissible $k$ (i.e. those with $n+k>k^{2}+1$) and found:

Exceptions (no k exists) for n<=200000:  [3, 7, 13, 23, 31, 113, 115]
For all other 2<=n<=200000, at least one k exists.
Maximum of the minimal such k in this range: 74 (attained at n=155933).

This is strong computational evidence that the statement might be true for all $n\ge 117$ (or perhaps all $n$ except the listed finite set), but it is not a proof.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. Every even $n\ge2$ has a solution (take $k=1$). For any $n$, any solution $k$ must satisfy $k^{2}-k+1<n$ (Lemma 2); and if $k^{2}\ge\sqrt{n+k}$ then a solution forces $n+k$ to be prime (Lemma 3).

(ii) First gap (crisp). For odd $n$, one needs an unconditional argument guaranteeing the existence of some $k\le (1+\sqrt{4n-3})/2$ with $n+k$ either prime or composite but with all prime factors $>k^{2}+1$. I do not have a method to force such a "$k^{2}$-rough" value in the short interval $[n+1,\,n+O(\sqrt n)]$.

(iii) Top 3 next moves. $1$ Try to prove a "rough numbers in short intervals" lemma tailored to the moving threshold $k^{2}$: show that among $n+1,\dots,n+\lfloor c\sqrt n\rfloor$ there is some $m=n+k$ with least prime factor $>k^{2}$. $2$ Investigate whether existing (unconditional) bounds on prime gaps in intervals of length $\asymp \sqrt n$ would imply the statement via Lemma 3. $3$ Extend computation much further (e.g. $n\le 10^{7}$) and record the distribution of the minimal witnessing $k$ for odd $n$; this may suggest a constructive pattern.

(iv) Minimal counterexample structure. A counterexample $n$ must be odd (since even $n$ work with $k=1$). It would require that for every admissible $k$ with $n+k>k^{2}+1$, the integer $n+k$ has a prime factor at most $k^{2}+1$.