Problem Statement
Let $\omega(n)$ count the number of distinct prime factors of $n$. What is the size of the largest interval $I\subseteq [x,2x]$ such that $\omega(n)>\log\log n$ for all $n\in I$?
Categories:
Number Theory
Progress
Erdős [Er37] proved that the density of integers $n$ with $\omega(n)>\log\log n$ is $1/2$. The Chinese remainder theorem implies that there is such an interval with\[\lvert I\rvert \geq (1+o(1))\frac{\log x}{(\log\log x)^2}.\]It could be true that there is such an interval of length $(\log x)^{k}$ for arbitrarily large $k$.Source: erdosproblems.com/452 | Last verified: January 15, 2026