Erdős Problem #945

declared status 'open'. Formalized: yes. 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? Current best: A problem of Erd\H{o}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\H{o}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\'{er'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. Prize: no. OEIS: A048892. Tags: divisors, number theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.