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

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

1. (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.

2. (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}$.

3. (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.

4. (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.

5. (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.

6. (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”](https://tenenb.perso.math.cnrs.fr/PPP/Erdos-100.pdf);

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+1Lemma 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:

1. some \(1\le k

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

2. $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

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 kThis 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(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

$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

1. $H(k)\ge p+k$ for every $k\ge G$; and

2. for every \(1\le k

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

Under (1), no $k\ge G$ can witness; under (2), no \(k

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

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