Longest run of consecutive integers with distinct divisor-counts: estimate $F(x)$ (Erdős #945)
Statement
Let $\tau(m)$ be the number of divisors of $m$. Let $F(x)$ be the largest $k$ for which there exist consecutive integers $n+1,\ldots,n+k\le x$ with $\tau(n+1),\ldots,\tau(n+k)$ all distinct. Estimate $F(x)$. In particular, is $F(x)\le(\log x)^{O(1)}$ — equivalently, is there a constant $C$ such that every interval $[x,\,x+(\log x)^C]$ contains two integers with the same number of divisors?
Acceptance. PARTIAL / EXTENDS: compute $F(x)$ for $x$ up to a large bound via a linear sieve for $\tau$, tabulate record runs and their locations, and fit $F(x)$ against $(\log x)^C$ to estimate the exponent $C$. FULLY RESOLVES: a proof that $F(x)\le(\log x)^{O(1)}$, or a construction forcing longer runs. Provide the sieve and the table of records.
Background
Erdős Problem #945 (Erdős–Mirsky 1952; also Er85e). The Erdős–Mirsky conjecture that $\tau(n)=\tau(n+1)$ infinitely often was proved by Heath-Brown (1984), but the quantitative run-length question $F(x)$ here is open. It is known $F(x)\to\infty$; whether it is polylogarithmic in $x$ (as conjectured) is unknown. $F(x)$ is directly computable by sieving $\tau$ over $[1,x]$ and measuring the longest all-distinct run. Entry: erdosproblems.com/945.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #945 (erdosproblems.com) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.