Does the ratio $f(2n)/f(n)$ tend to a limit, where $f(n)=\sum_{k\le n}\tau(2^k-1)$? (Erdős #893)
Statement
For a positive integer $m$ let $\tau(m)$ denote the number of divisors of $m$, and define $$f(n)=\sum_{1\leq k\leq n}\tau(2^k-1).$$ Does the ratio $f(2n)/f(n)$ tend to a limit as $n\to\infty$? Here the limit is understood in the extended sense: the problem is whether $f(2n)/f(n)$ converges to some value in $[0,\infty]$ (in particular whether it tends to $+\infty$), as opposed to oscillating without any limit.
Acceptance. FULLY RESOLVES: a complete rigorous proof (machine-checkable in Lean/Coq preferred, otherwise a full written proof) settling whether $f(2n)/f(n)$ tends to a limit — concretely, either a proof that $f(2n)/f(n)\to\infty$ (i.e. $\liminf_{n\to\infty} f(2n)/f(n)=\infty$), or a proof that the ratio does not tend to any limit, e.g. by exhibiting $\liminf f(2n)/f(n)<\infty$ alongside the known $\limsup=\infty$. The already-established facts — no finite limit and $\limsup=\infty$ [KoLu25] — may be cited but do not by themselves resolve the problem. ADVANCES: sharpen the known heuristic into a proof of an explicit unbounded lower bound $\liminf f(2n)/f(n)\geq g(n)$ for some $g(n)\to\infty$, strictly beyond what is proved in the background; OR extend the verified numerical evidence with a reproducible computation of $f(n)$ to a new record range, together with the factorization certificates for the relevant $2^k-1$. Deliver the proof file, or the search/factorization code plus the extended table and certificates.
Background
Posed by Erdős [Er98], who remarked that probably there is no simple asymptotic formula for $f(n)$ because it grows too fast. Listed as open on erdosproblems.com/893 (fetched 2026-07-13, status 'open'), tagged 'number theory | divisors'; the related sequence OEIS A046801 records the number of divisors of $2^n-1$, the summand of $f$. There has been decisive recent progress on the finite-limit version: Kovač and Luca [KoLu25], building on a heuristic found independently by Cambie, proved that $f(2n)/f(n)$ does NOT tend to a finite limit — in fact $\limsup_{n\to\infty} f(2n)/f(n)=\infty$ — and gave both theoretical and numerical evidence suggesting the stronger statement $\lim_{n\to\infty} f(2n)/f(n)=\infty$. What remains open, and keeps the problem listed as open, is whether this genuine (infinite) limit exists: does $f(2n)/f(n)\to\infty$ (equivalently $\liminf_{n\to\infty} f(2n)/f(n)=\infty$), or does the ratio oscillate with a finite liminf and an infinite limsup, so that no limit exists at all? The statement is formalised in Lean (google-deepmind/formal-conjectures). Attacker's tool: high-precision computation of $f(n)$, which requires factoring the numbers $2^k-1$ (feasible for $k$ into the low thousands using known Cunningham-project factorizations) to extend the numerical record for $f(2n)/f(n)$, combined with analytic control of the typical size of $\tau(2^k-1)$ via primitive-prime-divisor (Zsygmondy) and multiplicative-order heuristics.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #893 (T. F. Bloom) | website |
| REF-02 | OEIS A046801 — number of divisors of 2^n − 1 | website |
| REF-03 | Lean 4 formalisation (google-deepmind/formal-conjectures) of Erdős #893 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.