OPEN
This is open, and cannot be resolved with a finite computation.
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?\]
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)$.
View the LaTeX source
Additional thanks to: Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #122, https://www.erdosproblems.com/122, accessed 2026-01-16
