Restricted prime-factor counts over consecutive integers: a liminf bound and a limsup law (Erdős #890)
Statement
For an integer $n$ and a threshold $k\geq 1$, let $\omega_k(n)$ denote the number of distinct prime factors of $n$ that are $>k$, and let $\omega(n)$ denote the number of distinct prime factors of $n$ with no restriction. Two questions of Erdős and Selfridge. (1) Is it true that for every $k\geq 1$, $$\liminf_{n\to\infty}\sum_{0\leq i<k}\omega_k(n+i)\leq k?$$ (2) Is it true that $$\limsup_{n\to\infty}\left(\sum_{0\leq i<k}\omega(n+i)\right)\frac{\log\log n}{\log n}=1?$$
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, else a full written proof) settling both claims — that $\liminf_{n\to\infty}\sum_{0\leq i<k}\omega_k(n+i)\leq k$ for every $k\geq 1$, and that the stated limsup equals $1$. A proof of either claim in isolation is acceptable if clearly delimited. ADVANCES: prove the liminf bound for a specified infinite family of $k$, or for a new individual $k$ beyond the trivial cases, or improve the classical $\geq k-1$ lower bound to a strictly stronger statement; establish rigorous one-sided bounds on the limsup expression sharper than those implied by the classical maximal-order fact stated in background; or provide a reproducible computation over a stated range certifying the observed liminf/limsup behaviour, delivered with the exact search program and the attained record range. Deliver the proof (or machine-checkable formalisation) and/or the search code plus the attained range and the observed extremal values.
Background
Posed by Erdős and Selfridge [ErSe67, p.430]; listed as open on erdosproblems.com/890 (fetched 2026-07-21, status 'open'). They observed the matching lower bound $\liminf_{n\to\infty}\sum_{0\leq i<k}\omega_k(n+i)\geq k-1$ for every $k$; this follows from Pólya's theorem that the $k$-smooth integers have unbounded gaps, so that for all large $n$ all but at most one of $n,n+1,\ldots,n+k-1$ has a prime factor exceeding $k$. Question (2) rests on the classical maximal-order fact that $\limsup_{n}\omega(n)\frac{\log\log n}{\log n}=1$. Bloom flags an apparent error in the original [ErSe67], which stated the first question with $\omega$ in place of $\omega_k$ and with bound $k+\pi(k)$; as pointed out by Agustin Meza and Terence Tao in the site comments, that formulation is plainly false, and the corrected $\omega_k$ version with bound $k$ is what was intended. A Lean formalisation exists in the DeepMind formal-conjectures repository. No cash prize is attached. Attacker's tool: large-scale computation of $\sum_{0\leq i<k}\omega_k(n+i)$ over long ranges of $n$ to probe the liminf for each small $k$ (is it $k-1$ or $k$?), combined with sieve / smooth-number machinery (Pólya-type gap theorems) and the classical maximal-order estimate for $\omega$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #890 (T. F. Bloom) | website |
| REF-02 | Lean formalisation (DeepMind formal-conjectures) — Erdős #890 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.