Problem Statement
If $\omega(n)$ counts the number of distinct prime factors of $n$, then is it true that, for every $k\geq 1$,\[\liminf_{n\to \infty}\sum_{0\leq i<k}\omega(n+i)\leq k+\pi(k)?\]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?\]
Categories:
Number Theory Primes
Progress
A question of Erdős and Selfridge [ErSe67], who observe that\[\liminf_{n\to \infty}\sum_{0\leq i<k}\omega(n+i)\geq k+\pi(k)-1\]for every $k$. This follows from Pólya's theorem that the set of $k$-smooth integers has unbounded gaps - indeed, $n(n+1)\cdots (n+k-1)$ is divisible by all primes $\leq k$ and, provided $n$ is large, all but at most one of $n,n+1,\ldots,n+k-1$ has a prime factor $>k$ by Pólya's theorem.It is a classical fact that\[\limsup_{n\to \infty}\omega(n)\frac{\log\log n}{\log n}=1.\]
Source: erdosproblems.com/890 | Last verified: January 19, 2026