Problem Statement
Are there infinitely many $n$ such that, for all $k\geq 1$,\[ \omega(n+k) \ll k?\](Here $\omega(n)$ is the number of distinct prime divisors of $n$.)
Categories:
Number Theory
Progress
Related to [69]. Erdős and Graham [ErGr80] write 'we just know too little about sieves to be able to handle such a question ("we" here means not just us but the collective wisdom (?) of our poor struggling human race).'See also [679] and [826].
This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.
This has been resolved by Tao and Teräväinen [TaTe25], who have proved that there exists an absolute constant $C>0$ such that for infinitely many $n$, for all $k\geq 1$,\[\omega(n+k)\leq Ck.\]
Source: erdosproblems.com/248 | Last verified: January 14, 2026