Erdős–Selfridge: does the peak count of large 'new' prime factors $v_0(n)$ tend to infinity? (Erdős #889)
Statement
For integers $k\geq 0$ and $n\geq 1$, let $v(n,k)$ be the number of prime factors of $n+k$ that do not divide any of $n,n+1,\ldots,n+k-1$; equivalently, $v(n,k)$ counts the prime factors of $n+k$ that are greater than $k$. Put $$v_0(n)=\max_{k\geq 0}v(n,k).$$ Is it true that $v_0(n)\to\infty$ as $n\to\infty$? More generally, Erdős and Selfridge conjectured that for every fixed $l\geq 0$, $$v_l(n)=\max_{k\geq l}v(n,k)\to\infty$$ as $n\to\infty$.
Acceptance. FULLY RESOLVES (proof-shaped): a complete written or machine-checkable proof that $v_0(n)\to\infty$ as $n\to\infty$ (equivalently, that for every $m$ there is $N_m$ with $v_0(n)\geq m$ for all $n\geq N_m$), or a disproof exhibiting an infinite set of $n$ with $v_0(n)$ bounded; the stronger Erdős–Selfridge statement that $v_l(n)\to\infty$ for every fixed $l$ is the full target. ADVANCES (checkable milestones): prove $v_0(n)\geq 3$ for all sufficiently large $n$ — any explicit improvement over the recorded bound $v_0(n)\geq 2$ for $n\geq 17$ — or a lower bound $v_0(n)\geq g(n)$ with $g(n)\to\infty$, with proof; prove $v_1(n)\geq 2$ for all large $n$ (currently open); or a certified computation of $v_0(n)$ over a documented range establishing the least $n$ attaining each value $v_0(n)=2,3,4,\ldots$ with a reproducible program. Deliver the proof/formalisation or the search code with its certified output.
Background
A question of Erdős and Selfridge [ErSe67, p.428] (see also [Er98, p.178]); it is problem B27 in Guy's Unsolved Problems in Number Theory [Gu04] and is listed as open on erdosproblems.com/889 (fetched 2026-07-21, status 'open'). The known frontier is strikingly thin: Erdős and Selfridge could only show $v_0(n)\geq 2$ for $n\geq 17$, and for the more general conjecture they could not even prove $v_1(n)\geq 2$ for all large $n$. The statement has been formalised in Lean in the Google DeepMind Formal Conjectures project. An attacker would compute $v_0(n)$ (and $v_l(n)$) over large ranges — for each $n$, factor $n,n+1,n+2,\ldots$ and record the largest $v(n,k)$ — to map the growth empirically and locate the smallest $n$ with $v_0(n)\geq 3,4,\ldots$; the proof itself calls for sieve methods and results on prime factors in short intervals, and any resolution could be delivered as a Lean formalisation.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #889 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #889 (DeepMind Formal Conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.