Problem Statement
For which number theoretic functions $f$ is it true that, for any $F(n)$ such that $f(n)/F(n)\to 0$ for almost all $n$, there are infinitely many $x$ such that\[\frac{\#\{ n\in \mathbb{N} : n+f(n)\in (x,x+F(x))\}}{F(x)}\to \infty?\]
Categories:
Number Theory
Progress
Asked by Erdős, Pomerance, and Sárközy [EPS97] who prove that this is true when $f$ is the divisor function or the number of distinct prime divisors of $n$, but Erdős believed it is false when $f(n)=\phi(n)$ or $\sigma(n)$.Source: erdosproblems.com/122 | Last verified: January 13, 2026