Erdős Problems

Tags Prizes

OPEN

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?

#945: [ErMi52]

number theory, 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).\]

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.\]

Additional thanks to: Stijn Cambie