OPEN
This is open, and cannot be resolved with a finite computation.
Let $F(x)$ be the maximal $k$ such that there exist $n+1,\ldots,n+k\leq x$ with $\tau(n+1),\ldots,\tau(n+k)$ all distinct (where $\tau(m)$ counts the divisors of $m$). Estimate $F(x)$. In particular, is it true that\[F(x) \leq (\log x)^{O(1)}?\]In other words, is there a constant $C>0$ such that, for all large $x$, every interval $[x,x+(\log x)^C]$ contains two integers with the same number of divisors?
A problem of Erdős and Mirsky
[ErMi52], who proved that\[\frac{(\log x)^{1/2}}{\log\log x}\ll F(x) \ll \exp\left(O\left(\frac{(\log x)^{1/2}}{\log\log x}\right)\right).\]Erdős
[Er85e] claimed that the lower bound could be improved via their method 'with some more work' to $(\log x)^{1-o(1)}$. Beker
has improved the upper bound to\[F(x) \ll \exp\left(O\left((\log x)^{1/3+o(1)}\right)\right).\]Cambie has observed that
Cramér's conjecture implies that $F(x) \ll (\log x)^2$, and furthermore if every interval in $[x,2x]$ of length $\gg \log x$ contains a squarefree number (see
[208]) then every interval of length $\gg (\log x)^2$ contains two numbers with the same number of divisors, whence\[F(x) \ll (\log x)^2.\]See
[1004] for the analogous problem with the Euler totient function.
This problem is discussed in problem B18 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 05 October 2025.
Additional thanks to: Adrian Beker and 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 #945, https://www.erdosproblems.com/945, accessed 2026-01-16
