Problem Statement
Let $\epsilon>0$ and $\omega(n)$ count the number of distinct prime factors of $n$. Are there infinitely many values of $n$ such that\[\omega(n-k) < (1+\epsilon)\frac{\log k}{\log\log k}\]for all $k<n$ which are sufficiently large depending on $\epsilon$ only?
Can one show the stronger version with\[\omega(n-k) < \frac{\log k}{\log\log k}+O(1)\]is false?
Can one show the stronger version with\[\omega(n-k) < \frac{\log k}{\log\log k}+O(1)\]is false?
Categories:
Number Theory
Progress
One can ask similar questions for $\Omega$, the number of prime factors with multiplicity, where $\log k/\log\log k$ is replaced by $\log_2k$.See also [248] and [413].
In the comments DottedCalculator has disproved the second stronger version, proving that in fact for all large $n$ there exists $k<n$ such that\[\omega(n-k)\geq \frac{\log k}{\log\log k} + c\frac{\log k}{(\log\log k)^2}\]for some constant $c>0$.
Source: erdosproblems.com/679 | Last verified: January 16, 2026