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

Erdős problem #451 — wave 9j report

Date: 2026-07-28 (UTC)

Classification used below

(a) elementary-rigorous: proved below from definitions, CRT, or finite exact arithmetic.
(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the cited theorem.
(c) plausible/structural-unverified: heuristic or a proposed missing lemma, not a theorem.
(d) computational-only: exhaustive finite computation by the standalone checker, not a uniform theorem.

0. Mandatory live-page gate

I fetched the live page and its discussion through the Bright Data browser, not datacenter curl. The fetch was on 2026-07-28.

The exact current statement from the page's LaTeX view is:

Estimate $n_k$, the smallest integer $>2k$ such that $\prod_{1\leq i\leq k}(n_k-i)$ has no prime factor in $(k,2k)$.

Live status and collision markers:

Status: OPEN.
Last page edit: 21 June 2026.
Claimed proofs: 0.
Interested in collaborating: None.
Currently working on this problem: None.
Six comments were present.

Thus the requested stop condition did not apply.

The main page listed these known results:

Erdős and Graham: “we can prove $n_k>k^{1+c}$ but no doubt much more is true.”
Erdős expected $n_k>k^d$ for every fixed $d$, but $n_k<e^{o(k)}$.
Adenwalla's CRT construction gives the asymptotic upper bound

\[ n_k\leq\prod_{k<p<2k}p=e^{O(k)} \] (for the large-$k$ regime in which the displayed product is itself $>2k$).

van Doorn and Tang proved

\[ n_k>\exp\!\left(c\frac{(\log k)^2}{\log\log k}\right) \] for an absolute $c>0$.

The page links related problem #1095 and OEIS A386620.

I also read all six comments:

Woett, 19 Jun 2026: announced the human-written van Doorn–Tang paper. It proves, for all sufficiently large $k$, that every

\[ 2k<n\leq \exp\!\left(\frac{\log^2 k}{20\log\log k}\right) \] has a divisor prime $p\in(k,k+3k^{21/40})$ in the block product. The comment also links a Lean development.

Nat Sothanaphan, 19 Jun 2026: congratulated the authors and said the subsequent work gave confidence in the result.
Quanyu Tang, 26 Apr 2026: posted the earlier AI-produced draft claiming the superpolynomial lower bound, explicitly noting that he had not manually checked every detail.
Nat Sothanaphan, 27 Apr 2026: reported that a standard check found no issue with that draft.
Giorgos Kalogeropoulos, 2 Nov 2025: noted publication of OEIS A386620.
Quanyu Tang, 2 Oct 2025: gave the exact CRT density, its $\log 4$ asymptotic, data through $k=50$, and explicitly labelled the step from density to the first admissible integer as heuristic.

Sources: live page, LaTeX view, and discussion.

1. Literature verification

Original sources

The scanned Acta paper really contains the problem. On its p. 78 Erdős asks for the least endpoint of such a block, predicts superpolynomial but subexponential growth, and says that he could prove nothing nontrivial:

P. Erdős, Some unconventional problems in number theory, Acta Math. Acad. Sci.

Hungar. 33 (1979), 71–80. Primary PDF.

The Erdős–Graham monograph really contains the quoted lower bound on its p. 89:

P. Erdős and R. L. Graham, *Old and New Problems and Results in Combinatorial

Number Theory*, Monographie 28, 1980. Primary scan.

I OCR-checked the relevant scan page; it reads, modulo OCR subscripts: “Let $n_k$ denote the smallest integer ... We can prove $n_k>k^{1+c}$ but no doubt much more is true.”

A 1981 Erdős survey states a shifted-block version of the same question and says only rough upper and lower bounds were available:

P. Erdős, Problems and Results in Number Theory (1981),

primary PDF, pp. 7–8 of the scan.

Current theorem

The cited paper and arXiv identifier exist:

W. van Doorn and Q. Tang, Consecutive integers free of certain prime factors,

arXiv:2606.19863, submitted 18 June 2026.

Its Theorem 1.1 says that, for all sufficiently large $k$ and

2k<n\leq \exp\!\left(\frac{\log^2 k}{20\log\log k}\right),

the product $(n-k)\cdots(n-1)$ is divisible by a prime $p\in(k,k+3k^\theta)$, where one may take $\theta=21/40$. For large $k$, that interval lies inside $(k,2k)$. Therefore (b)

n_k>\exp\!\left(\frac{\log^2 k}{20\log\log k}\right) \quad(k\ \text{sufficiently large}).

The named external inputs are the Baker–Harman–Pintz short-interval prime theorem and Konyagin's rational-approximation estimate. This proves Erdős's superpolynomial lower-growth prediction, but not the requested upper estimate, so the main problem remains open.

Density note and computation

Tang's note exists and says exactly what the comment attributes to it:

Q. Tang, Notes on Erdős Problem #451: Density Estimates and Heuristic Evidence,

primary repository PDF, 2 October 2025.

It proves the density asymptotic and reports exact experiments through $k=50$, while explicitly declining to infer a theorem about $n_k$ from the density.

OEIS A386620 currently links a b-file through $k=183$, last modified 25 July 2026. I use its first 110 values only as candidate certificates; the checker below independently proves their admissibility and minimality. I do not adopt the minimality of entries 111–183 as an independently verified claim here.

Exact-title and exact-statement searches located the sources above but no other primary paper giving a stronger upper or lower asymptotic for this specific function. I also full-text searched Gérald Tenenbaum's 2013 survey Some of Erdős' unconventional problems in number theory, thirty-four years later; I found no treatment of this particular least-block problem. These are search misses, not a proof that no other literature exists.

2. Exact elementary reduction

Let

\mathcal P_k=\{p:p\text{ prime},\ k<p<2k\},\qquad M_k=\prod_{p\in\mathcal P_k}p.

Residue lemma

(a) For $p\in\mathcal P_k$, the block $[n-k,n-1]$ contains a multiple of $p$ if and only if

n\bmod p\in\{1,\ldots,k\}.

Indeed, if $r=n\bmod p$ lies in $1,\ldots,k$, then $n-r$ is the required multiple. If $r=0$, the previous multiple is $n-p<n-k$; if $r>k$, the previous multiple $n-r$ is again below the block.

Consequently, (a) $n$ is admissible exactly when

n\bmod p\in S_p:=\{0,k+1,\ldots,p-1\} \quad\text{for every }p\in\mathcal P_k. \tag{2.1}

There are $p-k$ allowed residues for $p$.

Exact density

CRT now gives (a) exactly

A_k:=\#\{n\bmod M_k:n\text{ is admissible}\} =\prod_{p\in\mathcal P_k}(p-k),

and hence

D_k:=\frac{A_k}{M_k} =\prod_{k<p<2k}\left(1-\frac{k}{p}\right). \tag{2.2}

Using the prime number theorem with its standard de la Vallée Poussin error term, partial summation turns

\log D_k^{-1}=\sum_{k<p<2k}\log\frac p{p-k}

into (b)

\log D_k^{-1} =\frac{k}{\log k}\int_1^2\log\frac{t}{t-1}\,dt O\!\left(\frac{k}{(\log k)^2}\right).

The integral is

\int_1^2(\log t-\log(t-1))\,dt=2\log2=\log4,

so (b)

\log D_k^{-1} =(\log4)\frac{k}{\log k} O\!\left(\frac{k}{(\log k)^2}\right). \tag{2.3}

The checker verifies (2.1) directly against the original product for $k\leq20,n\leq500$, and verifies the exact one-period count (2.2) by enumeration for $k\leq15$.

A useful transition lemma

(a) If $\mathcal P_{k+1}=\mathcal P_k$, every $(k+1)$-admissible endpoint is $k$-admissible, because its longer block contains the last $k$ entries. Thus $n_{k+1}\geq n_k$.

Moreover:

if $n_k$ is already $(k+1)$-admissible, then $n_{k+1}=n_k$;
otherwise, if $n_k$ is coprime to $M_k$ and $n_k+1>2(k+1)$, then

$n_k+1$ is $(k+1)$-admissible, because its block is the old clean block plus $n_k$. Hence $n_{k+1}=n_k+1$.

The checker tests all 42 unchanged-prime-set instances occurring in its exact table.

3. Exhaustive CRT-wheel computation

Why this is an exact certificate

A linear scan is unsuitable once candidates reach $10^{12}$ or more. Instead, select a prefix $W\subset\mathcal P_k$. Starting from residue $0\bmod1$, the code extends each existing CRT residue by every member of $S_p$ for $p\in W$. The resulting list contains exactly

\prod_{p\in W}(p-k)

distinct residues modulo $\prod_{p\in W}p$, and therefore contains every integer that could satisfy the primes in $W$. Every occurrence of every such residue in the target interval is then tested against every remaining prime. A negative answer is exhaustive.

The core is:

def admissible(k, n, primes):
    return n > 2*k and all((r := n % p) == 0 or r > k for p in primes)

residues, modulus = [0], 1
for p in wheel_primes:
    inverse = pow(modulus, -1, p)
    allowed = [0, *range(k + 1, p)]
    residues = [
        old + modulus * ((target - old) * inverse % p)
        for old in residues for target in allowed
    ]
    modulus *= p

The full dependency-free implementation is erdos451_wave9j_verify.py.

Exact table, $1\leq k\leq110$

(d) The checker verifies the following values, including exhaustive minimality:

  1-- 10: 3, 6, 9, 20, 13, 21, 21, 22, 65, 220
 11-- 20: 51, 338, 133, 321, 339, 340, 113, 114, 368, 550
 21-- 30: 805, 2691, 1884, 2664, 7653, 7654, 36887, 36888, 21234, 21235
 31-- 40: 3477, 30783, 30784, 48543, 48544, 579124, 93436, 248622, 248623, 1702197
 41-- 50: 743211, 1124708, 59406, 59407, 241250, 241251, 235635, 235636, 771891, 771892
 51-- 60: 3734167, 16769624, 624572, 10127641, 109283691, 109283692, 285521236, 2056985086, 13040275, 59177076
 61-- 70: 3708179, 3708180, 59177077, 134271082, 137559374, 1047108495, 51405135, 51405136, 1156433515, 8424261612
 71-- 80: 1047108495, 1156433515, 15168078, 15168079, 133861152, 133861153, 1296733729, 1568382023, 133861153, 161980972
 81-- 90: 1296733733, 9353778956, 361587771, 4668429670, 6856310353, 6856310354, 6856310355, 124914730611, 915999805, 3155797315
 91--100: 38616024366, 38616024367, 325357253140, 325357253141, 325357253142, 664515187589, 382032219523, 1972377590897, 8639673742078, 21576974095890
101--110: 985294036250, 7779486350688, 52925096059, 52925096060, 2081954537493, 13706889817679, 63465168467, 763417797000, 227926760, 227926761

The certificate exhaustively tested 19,087,278 wheel candidates. Its largest wheel had 1,171,456 residue classes. For $k\leq30$, a deliberately separate direct product scan gives the same results.

Extension of the density experiment

Tang reported, for $k\leq50$,

\min n_kD_k=0.1348969668\quad(k=46),\qquad \max n_kD_k=7.7721101000\quad(k=23).

Using exact rational $D_k$ and the independently certified table:

(d) on $2\leq k\leq110$, the minimum moves to

\[ n_{110}D_{110}=0.0119690427373\ldots, \] while the maximum remains $7.77211009956\ldots$ at $k=23$;

(d) Tang's finite observation

\[ \log n_k\leq(\log4)\frac{k}{\log k}\qquad(k\leq50) \] fails in the certified extension exactly at \[ k=58,\ 70,\ 100 \quad\text{among }2\leq k\leq110. \]

The comparisons use 60-digit decimal logarithms in the checker. This does not disprove the asymptotic conjecture with a $+o(1)$ term; it only shows that the bare finite inequality and the “first hit is one mean spacing” model fluctuate substantially.

A concrete frontier bound

OEIS currently ends at $k=183$, so I also ran the same exhaustive method for $k=184$. The wheel used

W=\{191,193,197,199,211\},

with allowed-set sizes $7,9,13,15,27$. Thus it has exactly

7\cdot9\cdot13\cdot15\cdot27=331\,695

residues modulo

191\cdot193\cdot197\cdot199\cdot211=304\,924\,579\,879.

After filtering 108,779,361 resulting candidates against the other 26 primes:

\boxed{n_{184}>10^{14}} \tag{3.1}

is proved (d). This is unconditional finite exhaustion from $369=2\cdot184+1$ through $10^{14}$.

The current OEIS b-file reports

n_{183}=S:=167\,981\,058\,401\,851\,841.

My checker independently verifies that $S$ is 183-admissible but does not recertify its minimality. At $k=184$, $S$ fails exactly because

S\bmod191=S\bmod197=184.

Also (a) $\mathcal P_{184}=\mathcal P_{183}\cup\{367\}$, so every 184-admissible endpoint is 183-admissible. Thus, conditional on the published equality $S=n_{183}$, no 184-admissible endpoint can lie below $S$. The checker also exhausts another 10,877,975 wheel candidates and proves (d) that there is no 184-admissible integer in

[S,S+10^{13}].

Consequently, accepting the externally published minimality of $S=n_{183}$ would give $n_{184}>S+10^{13}$. I leave this explicitly conditional and do not count it as an independently certified global lower bound; (3.1) is the unconditional result.

4. Reproduction

Run:

python3 runs/erdos451_wave9j_verify.py

Final output:

exact through k=10: n_k=220; wheel=3 residues; tested=3
exact through k=20: n_k=550; wheel=27 residues; tested=16
exact through k=30: n_k=21235; wheel=7 residues; tested=128
exact through k=40: n_k=1702197; wheel=21 residues; tested=430
exact through k=50: n_k=771892; wheel=297 residues; tested=1199
exact through k=60: n_k=59177076; wheel=1001 residues; tested=2794
exact through k=70: n_k=8424261612; wheel=6669 residues; tested=18570
exact through k=80: n_k=161980972; wheel=9639 residues; tested=21567
exact through k=90: n_k=3155797315; wheel=17017 residues; tested=497359
exact through k=100: n_k=21576974095890; wheel=66339 residues; tested=822061
exact through k=110: n_k=227926761; wheel=28917 residues; tested=25589
all checks passed
exact table: k=1..110
table wheel candidates exhaustively tested: 19087278
largest table wheel: 1171456 residues
unchanged-prime transition instances checked: 42
k=2..110 density diagnostics: min(n_k*D_k)=0.0119690427373 at k=110; max=7.77211009956 at k=23
log(n_k) > log(4)*k/log(k) exactly at k=58,70,100 within 2<=k<=110
k=184: no admissible n in [369,10^14] and none in [167981058401851841,167991058401851841]
k=184 wheel=331695 residues; tested base/gap candidates=108779361/10877975
elapsed_seconds=32.867

Measured with /usr/bin/time -v: 32.91 seconds wall time, 32.66 CPU seconds, and 148,984 KiB maximum resident memory. Script SHA-256:

24f9a4a9139b05566eba576a5df8e00bad4377ce9fffae9ea50668e24fdd505d

5. Exact remaining wall

The CRT density is a statement over the complete period

M_k=\prod_{k<p<2k}p=\exp((1+o(1))k).

It gives an average spacing $D_k^{-1}$, but it gives no bound on the first gap after $2k$. This is precisely the unjustified step in the heuristic.

A sufficient missing lemma for Erdős's desired subexponential upper bound would be:

There is an absolute $C$ such that the initial interval $[2k+1,D_k^{-C}]$ contains an admissible integer for all sufficiently large $k$.

Because (2.3) gives $D_k^{-C}=\exp(O(k/\log k))=e^{o(k)}$, such a lemma would prove the desired upper side. The sharper heuristic would require an initial-interval result at length $D_k^{-1+o(1)}$.

This proposed lemma is (c), not proved here. Ordinary density, a first-moment argument over the full CRT period, and the tested SAT/CRT machinery do not supply the needed uniform initial-interval discrepancy bound. Computationally, a direct scan has cost proportional to the endpoint; the wheel replaces this by the number of partial CRT survivors, but at the current $k=183/184$ frontier that count still grows into the billions well before the expected first-hit scale. A finite computation cannot provide the uniformity in $k$ needed to close the problem.

PARTIAL: exact CRT reduction and density verified; n_k certified for 1<=k<=110; n_184>10^14 certified; the unresolved step is a uniform initial-interval hit bound such as n_k<=D_k^{-C}.

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