Must every length-$p_1\cdots p_k$ interval contain an integer with $>k$ prime factors? (Erdős #891)
Statement
Let $2=p_1<p_2<\cdots$ be the sequence of primes and fix an integer $k\geq 2$. Is it true that, for all sufficiently large $n$, the interval $$[\,n,\ n+p_1p_2\cdots p_k\,)$$ of $p_1\cdots p_k$ consecutive integers must contain an integer with more than $k$ prime factors (counted with multiplicity)? The first open case is $k=2$, where $p_1p_2=6$: is it true that every interval of $6$ sufficiently large consecutive integers contains one with at least $3$ prime factors?
Acceptance. FULLY RESOLVES (proof-shaped): a complete written or machine-checkable proof that for each fixed $k\geq 2$ every interval $[n,n+p_1\cdots p_k)$ with $n$ large contains an integer with more than $k$ prime factors, or a disproof producing, for some $k$, infinitely many intervals of length $p_1\cdots p_k$ in which every integer has at most $k$ prime factors. Settling the single case $k=2$ (every $6$ large consecutive integers include one with $\geq 3$ prime factors) counts as fully resolving that case. ADVANCES (checkable): prove the statement with the interval length improved below Schinzel's $p_1\cdots p_{k-1}p_{k+1}$ toward the target $p_1\cdots p_k$, with proof; establish a conditional resolution under a clearly stated hypothesis (e.g. a quantified prime $k$-tuples / Dickson-type input), flagged as conditional; or a certified computation reporting, over a documented range and for small $k$, the longest run of consecutive integers each with at most $k$ prime factors, bounding how large $n$ can be while a length-$p_1\cdots p_k$ counterexample persists. Deliver the proof/formalisation or the reproducible search code with certified output.
Background
A question of Erdős and Selfridge [ErSe67, p.430]; listed as open on erdosproblems.com/891 (fetched 2026-07-21, status 'open'). Schinzel deduced from Pólya's theorem [Po18] — that the integers built from a fixed finite set of primes have unbounded gaps — that the statement holds if the interval length $p_1\cdots p_k$ is replaced by the slightly larger $p_1\cdots p_{k-1}p_{k+1}$. The sharp version is open even for $k=2$: it is not known whether every interval of $6$ large consecutive integers contains an integer with at least $3$ prime factors. On the other side, Weisenberg observed (via Dickson's conjecture) that the analogous claim fails if the length is reduced by one to $p_1\cdots p_k-1$: writing $L_k=\operatorname{lcm}\{1,\ldots,p_1\cdots p_k\}$, Dickson's conjecture yields infinitely many $n'$ with $\tfrac{L_k}{m}n'+1$ prime for every $1\leq m<p_1\cdots p_k$, and then $n=L_kn'+1$ makes every integer in $[n,n+p_1\cdots p_k-1)$ have at most $k$ prime factors — so the interval length $p_1\cdots p_k$ is exactly the contested threshold. The statement is formalised in Lean in the Google DeepMind Formal Conjectures project. An attacker would combine sieve bounds and results on the distribution of $k$-almost-primes in short intervals, and computationally scan large ranges for long runs of integers each having at most $k$ prime factors to probe how close to the threshold counterexamples can reach.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #891 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #891 (DeepMind Formal Conjectures) | website |
| REF-03 | Dickson's conjecture (Wikipedia) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.