A problem of Erdős and Mirsky [ErMi52]. More generally, they ask about the estimation of the longest run of consecutive integers $\leq x$ which have the same number of divisors.

Spiro [Sp81] proved that there are infinitely many $n$ such that $\tau(n)=\tau(n+5040)$, and Heath-Brown [He84] improved her method to prove this for $\tau(n)=\tau(n+1)$. More generally, he showed that the number of such $n\leq x$ is\[\gg \frac{x}{(\log x)^7}.\]This lower bound was improved to\[\gg \frac{x}{(\log\log x)^3}\]by Hildebrand [Hi87]. Erdős, Pomerance, and Sárközy [EPS87] proved an upper bound of\[\ll\frac{x}{\sqrt{\log\log x}}.\]The true count is likely asymptotic to\[c\frac{x}{\sqrt{\log\log x}}\]for some constant $c>0$. This has been established for almost all $x$ by Tao and Teräväinen [TaTe25].

See [1003] for the analogous question with the Euler totient function.

This is discussed in problem B18 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 02 December 2025.