Problem Statement
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?
Categories:
Number Theory Divisors
Progress
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].
Source: erdosproblems.com/945 | Last verified: January 19, 2026