Erdoes #680 - working report - Erdős Problem a Day

Erdős problem #680 — exact reduction and verification through $10^9$

Access/search date: 2026-07-27 (UTC).

Claim labels used throughout:

(a) elementary-rigorous: proved below from definitions and elementary arithmetic.
(b) rigorous-modulo-named-theorem: the deduction is rigorous, conditional only on the cited published theorem.
(c) plausible/structural-unverified: heuristic, conjectural, or an unverified preprint claim.
(d) computational-only: exhaustive only in the explicitly stated finite range.

Step 0: live-page gate

I fetched the rendered live page erdosproblems.com/680 through the Bright Data browser path (direct datacenter requests returned HTTP 403). (a, documentary verification) At access time the page showed:

status OPEN;
0 comments on this problem;
0 claimed proofs for this problem;
Currently working on this problem: None;
Interested in collaborating: None.

Thus the mandatory stop condition did not fire.

Verbatim live statement

Is it true that, for all sufficiently large $n$, there exists some $k$ such that \[ > p(n+k)>k^2+1, > \] where $p(m)$ denotes the least prime factor of $m$?
Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?

The $+C_\epsilon$ is outside the exponential. This is also how the current page history and the page-linked formal statement render it.

Known results/text listed on the live page

(c, as explicitly described there as assumptions/heuristics) The page says that the first assertion, and the version with $k^2$ replaced by $k^d$ for any $d$, follow from “plausible assumptions on the distribution of primes,” and that the challenge is an unconditional proof.

(b conditional on Cramér's conjecture, as stated on the page) With $p_1<p_2<\cdots$ denoting the primes, the page records Erdős's observation that

\limsup_{j\to\infty}\frac{p_{j+1}-p_j}{(\log j)^2}=1

implies that for every $\epsilon>0$ and every sufficiently large $n$, some $k$ satisfies

p(n+k)>e^{(1-\epsilon)\sqrt{k}}.

(c, heuristic) The page cites Granville's refinement and suggests replacing the coefficient $1+\epsilon$ in the second question by $2e^{-\gamma}+\epsilon$. The live page prints $2e^{-\gamma}\approx1.119\ldots$. A from-scratch Euler--Maclaurin computation in the verifier gives

2e^{-\gamma}=1.122918967134\ldots,

so the displayed decimal on the page appears to be a typo; the exact constant on the page is unaffected. (d for the decimal check)

The page also points to problems #681 and #682.

Literature check

(a, documentary verification) The page's [Er79d] is P. Erdős,

“Some unconventional problems in number theory,” Acta Math. Acad. Sci. Hungar. 33 (1979), 71–80. The primary scan, pp. 73–74, defines $B(n,g)$ to be the least $i$ with $p(n+i)>g(i)$, poses the $i^2+1$ question, and explicitly identifies the obstruction in the exponential upper direction: a composite $n+i$ can have a large least prime factor even when prime gaps are controlled.

(a, documentary verification; c for the heuristic) The live

bibliography entry [Gr95] is Andrew Granville, “Harald Cramér and the distribution of prime numbers”, Scandinavian Actuarial Journal (1995), 12–28, DOI 10.1080/03461238.1995.10413946. Granville's own publication page says the heuristic changes the lower prediction for some maximal gaps from $1$ to $2e^{-\gamma}$.

(b) Baker, Harman and Pintz,

“The Difference Between Consecutive Primes, II”, Proc. London Math. Soc. 83 (2001), 532–562, prove that $[x-x^{0.525},x]$ contains a prime for all sufficiently large $x$. A current preprint by Runbo Li, arXiv:2308.04458v8, claims $0.52$; it has no journal reference on arXiv, so I record the claimed improvement as (c), not as an established theorem. Either exponent remains strictly larger than the $1/2$ needed by the prime-only reduction below.

(b) Ford, Green, Konyagin, Maynard and Tao,

“Long gaps between primes”, J. Amer. Math. Soc. 31 (2018), 65–105, prove \[ G(X)\gg \frac{\log X\,\log_2X\,\log_4X}{\log_3X}. \] This is $o((\log X)^2)$, so it is too short for the necessary Cramér-scale gaps in the second question derived below.

(c; not used) A very recent unrefereed preprint, Cheng-Ting Wang,

arXiv:2605.14871v5, claims $p_{j+1}-p_j<(13/3)\log^2p_j$. ArXiv lists no journal reference and adds an administrative substantial-text-overlap note. If valid, this much stronger claim would settle the first question through Lemma 2 below, but I did not validate its proof and the authoritative live problem page still records zero claimed proofs. It is therefore not treated as a theorem.

(a, search miss rather than a mathematical assertion) Exact-phrase

searches for p(n+k)>k^2, B(n,g), and the position-dependent exponential least-prime-factor condition found the original paper and the problem page, but no later paper directly resolving this problem. I also searched the full text of Gérald Tenenbaum's 2013 survey “Some of Erdős' unconventional problems in number theory, thirty-four years later”; it does not revisit this $B(n,g)$ passage. This is only a report of the search, not a completeness theorem for the literature.

An exact elementary reduction

Write $\ell(m)$ for the least prime factor of $m$, and let

q(n)=\min\{q>n:q\text{ is prime}\},\qquad d(n)=q(n)-n.

Thus $n+1,\ldots,n+d(n)-1$ are composite.

Lemma 1: finite stopping bound

(a) If

k^2-k+1\ge n,

then $n+k\le k^2+1$, and hence $\ell(n+k)\le n+k\le k^2+1$. Since $k^2-k+1$ is increasing for $k\ge1$, no such $k$, or any later $k$, can be a witness. Therefore an exact search for a fixed $n$ only has to test

1\le k\le K(n):=\max\{k:k^2-k+1<n\}.

Lemma 2: next-prime/rough-composite dichotomy

(a) The original inequality has a witness for $n$ if and only if at least one of the following holds:

some $1\le k<d(n)$ satisfies

$\ell(n+k)>k^2+1$ (necessarily a rough composite); or

$n>d(n)^2-d(n)+1$, in which case $k=d(n)$ and the next prime

$q(n)$ is a witness.

Proof. For $k=d=d(n)$,

\ell(n+d)=n+d>d^2+1 \quad\Longleftrightarrow\quad n>d^2-d+1.

If this fails, then $n\le d^2-d+1$, and monotonicity gives $n\le k^2-k+1$ for every $k\ge d$. Lemma 1 rules out every such $k$. The only remaining possible witnesses have $k<d$, where $n+k$ is composite. Conversely, either displayed alternative directly supplies a witness. $\square$

Equivalently, (a) $n$ is an exception precisely when

n\le d(n)^2-d(n)+1 \quad\text{and}\quad \ell(n+k)\le k^2+1\quad(1\le k<d(n)).

This isolates the two independent obstructions: an approximately $\sqrt n$-long prime-free interval and no sufficiently rough composite inside it.

Two immediate consequences are:

(a) Every even $n\ge2$ has the witness $k=1$, since $n+1$ is odd

and $\ell(n+1)\ge3>2$.

(a) A uniform theorem $d(n)<\frac{1+\sqrt{4n-3}}2$ for all sufficiently

large $n$ would settle the first question using only the next prime. The published $O(n^{0.525})$ prime-gap theorem, and even the claimed $O(n^{0.52})$ preprint, do not reach this square-root threshold.

Lemma 3: one inequality certifies a whole prime gap

Let $p<q$ be consecutive primes and $G=q-p$. (a) If

\[ p>G^2-G+1, \]

then every integer $n\in[p,q)$ has the next-prime witness

k=q-n,\qquad \ell(n+k)=q>k^2+1.

Indeed $k\le G$, $k^2-k+1\le G^2-G+1<p\le n$, and rearranging gives $q=n+k>k^2+1$.

This gap-level certificate is much cheaper and less error-prone than factoring every $n+k$.

Exact finite computation

Result

(d) Exhaustive from-scratch sieving proves:

\boxed{\text{For every }116\le n\le10^9,\text{ the next prime }q>n \text{ gives }k=q-n\text{ with }q>k^2+1.}

(d) The exact integers $2\le n\le10^9$ having no witness at all are

\boxed{3,\,7,\,13,\,23,\,31,\,113,\,115.}

This finite statement does not prove the asymptotic conjecture.

Human-checkable certificates for the seven exceptions

The row for $n$ lists the complete vector $(\ell(n+1),\ldots,\ell(n+K(n)))$. Lemma 1 proves that later $k$ cannot work. (a) for interpreting each certificate; d for discovering/exhaustively classifying the list)

$n$	$K(n)$	complete least-factor vector
3	1	$2$
7	2	$2,3$
13	3	$2,3,2$
23	5	$2,5,2,3,2$
31	5	$2,3,2,5,2$
113	11	$2,5,2,3,2,7,2,11,2,3,2$
115	11	$2,3,2,7,2,11,2,3,2,5,2$

Every entry in position $k$ is at most $k^2+1$.

Full-range gap certificate

The standalone verifier uses an odd-only bit Eratosthenes sieve, built from scratch, and checks Lemma 3 for every consecutive prime gap with left endpoint at least $127$. It separately trial-divides every candidate for $2\le n\le126$. (d)

checked quantity	exact output
range	$116\le n\le1,000,000,000$
consecutive gaps checked	$50,847,504$
first prime after $10^9$	$1,000,000,007$
largest gap encountered	$436273009\to436273291$, length $282$
smallest $p-(G^2-G+1)$	$48$, at $139\to149$
largest $(G^2-G+1)/p$	$1123/1327<1$, at $1327\to1361$

The last row is a compact extremal summary of all the gap inequalities, not a replacement for enumerating them; the checker performs the enumeration.

As an independent cross-check, erdos680_scan.cpp builds a full least-prime- factor array by a linear sieve and tests every admissible pair $(n,k)$ directly. At $10^9$ it returned the same seven exceptions. Its output SHA-256 was c968a2bab2a3762a06b1e13fd86488f572391db0377ebe3eed5fca94f0f6fbe1. (d)

The exponential question: exact necessary condition and wall

Fix $a=1+\epsilon>1$ and $C>0$, and put

H(k)=e^{a\sqrt{k}}+C.

Suppose $n$ has no witness for this threshold, and again let $q=n+d$ be the next prime. Since $\ell(q)=q$, failure at $k=d$ gives

n+d=q\le e^{a\sqrt d}+C.

Consequently, whenever $n\ge C$ (so the logarithm below is nonnegative),

\boxed{d\ge \frac{\log^2(n+1-C)}{a^2}.}

This is (a). Thus infinitely many counterexamples for fixed $(\epsilon,C)$ force infinitely many prime gaps of Cramér scale, with asymptotic leading constant at least $1/(1+\epsilon)^2$.

That necessary prime gap is still not sufficient. (a) An exact sufficient lemma for the desired negative answer would be the following weighted-gap statement: for every $a>1$, there is a fixed $C$ and infinitely many consecutive primes $p<q=p+G$ such that

$H(k)\ge p+k$ for every $k\ge G$; and
for every $1\le k<G$, some prime

$r_k\le H(k)$ divides $p+k$.

Under (1), no $k\ge G$ can witness; under (2), no $k<G$ can witness. So these two explicit conditions would produce the required counterexamples.

The exact missing input is therefore not merely “large prime gaps,” but Cramér-scale gaps with a position-dependent small-factor covering of every internal composite. The published Ford--Green--Konyagin--Maynard--Tao gap length is

\gg\frac{\log p\,\log_2p\,\log_4p}{\log_3p} =o((\log p)^2),

and hence misses even the necessary length before the weighted factor condition is considered. (b) This also explains Erdős's warning that Cramér's conjecture alone does not control rough composites.

What is and is not proved

(a) There is an exact dichotomy reducing the first question to a

square-root next-prime condition or a rough composite before the next prime.

(d) The assertion is true for every $116\le n\le10^9$, always with

the next prime as a witness; the only exceptions through $10^9$ are the seven listed small integers.

(a)+(b) A square-root-scale uniform upper bound for next-prime gaps

would close the first question, but the established exponent $0.525$ remains on the wrong side of $1/2$.

(a)+(b) The second question requires both an unproved

$\asymp\log^2 n$ lower gap and an unproved weighted internal-factor covering. Current large-gap machinery supplies neither at that scale.

(d) Extending the finite check cannot supply the uniform asymptotic

step. The present bit sieve used 62.8 MB and 5.55 seconds at $10^9$. Straight scaling to $10^{12}$ would require a segmented implementation and roughly 1.5–3 single-core hours on this VM (about \$0.15–\$0.30 at \$0.10/core-hour); it would still prove only a finite bound.

Reproduction

Standalone verifier: erdos680_wave6i_verify.py

Direct full-SPF cross-check: erdos680_scan.cpp

The verifier SHA-256 is 3d93b5a87a6f0168585e444293978a7bd89ad78a51fbb174dc9744225e384caf. It uses only Python's standard library plus a C11 compiler and downloads no prime table.

python3 runs/erdos680_wave6i_verify.py

Observed full output:

small_trial_division=PASS
small_exceptions=3,7,13,23,31,113,115
finite_stop_bound=PASS
gap_monotonicity=PASS
two_exp_minus_gamma=1.122918967134
limit=1000000000
sieve_limit=1000031624
checked_gaps=50847504
first_prime_after_limit=1000000007
maximum_gap=282 left=436273009 right=436273291
minimum_slack=48 left=139 right=149
maximum_obstruction_ratio=1123/1327 left=1327 right=1361
gap_certificate=PASS
conclusion=for every 116 <= n <= 1000000000, the next prime q gives k=q-n and q>k^2+1
ALL_CHECKS_PASS

The recorded run took 5.55 seconds wall time and 62,792 KiB peak RSS. (d)

PARTIAL: Exact reduction obtained; the first assertion holds for every $116\le n\le10^9$ (next-prime witness), with exactly seven smaller exceptions, while the uniform square-root gap step and the exponential question's Cramér-scale weighted-covering lemma remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger

\(n\)	\(K(n)\)	complete least-factor vector
3	1	\(2\)
7	2	\(2,3\)
13	3	\(2,3,2\)
23	5	\(2,5,2,3,2\)
31	5	\(2,3,2,5,2\)
113	11	\(2,5,2,3,2,7,2,11,2,3,2\)
115	11	\(2,3,2,7,2,11,2,3,2,5,2\)

checked quantity	exact output
range	\(116\le n\le1,000,000,000\)
consecutive gaps checked	\(50,847,504\)
first prime after \(10^9\)	\(1,000,000,007\)
largest gap encountered	\(436273009\to436273291\), length \(282\)
smallest \(p-(G^2-G+1)\)	\(48\), at \(139\to149\)
largest \((G^2-G+1)/p\)	\(1123/1327<1\), at \(1327\to1361\)

Erdős problem #680 — exact reduction and verification through \(10^9\)