Erdoes #893 - working report - Erdős Problem a Day

Erdős problem #893 — wave 7s

Date checked: 2026-07-28 UTC

0. Mandatory live-page check

(d, live-page observation) I fetched

the live problem page and its

LaTeX view through the Bright Data

browser, not by datacenter curl. The rendered page and document.body.innerText

agreed.

(d, live-page observation) The live page's statement, verbatim from its

LaTeX view, is:

> If $\tau(n)$ counts the divisors of $n$ then let\[f(n)=\sum_{1\leq k\leq n}\tau(2^k-1).\]Does $f(2n)/f(n)$ tend to a limit?

(d, live-page observation) Live metadata observed before doing mathematics:

Status: OPEN.
Comments: 0.
Claimed proofs: 0.
Interested in collaborating: None.
Currently working on this problem: None.
“I am working on formalising the results on this problem”: None.
Likes: Vjeko_Kovac.
“This problem looks difficult”: Vjeko_Kovac.
“This problem looks tractable”: None.
“The results on this problem could be formalisable”: None.
Formalised statement: Yes.
Related OEIS sequence: A046801 (possible).

(d, live-page observation) Thus neither stop condition (claimed

proof/solved/falsified, or current worker) was present.

(d for the page transcription; b for the cited theorem) The live page lists

these known results:

Erdős [Er98] says that “probably there is no simple asymptotic formula for

$f(n)$ since $f(n)$ increases too fast.”

Kovač and Luca [KoLu25] (building on a heuristic independently found by

Stijn Cambie, personal communication) proved

\[ \limsup_{n\to\infty}\frac{f(2n)}{f(n)}=\infty, \]

and give theoretical and numerical evidence for the still-unproved

\[ \frac{f(2n)}{f(n)}\longrightarrow\infty. \]

1. Literature check and exact current frontier

(d, bibliographic check) The original item really is P. Erdős, “Some of my

new and almost new problems and results in combinatorial number theory,”

Number Theory (Eger, 1996) (1998), pp. 169–180,

DOI 10.1515/9783110809794.169.

The current primary paper quotes the question from p. 180.

(b, rigorous modulo the cited paper) The page's KoLu25 reference is

Vjekoslav Kovač and Florian Luca,

“On the number of divisors of Mersenne numbers,” arXiv:2506.04883v4.

Version 1 was submitted 2025-06-05 and the current v4 was posted 2026-02-03.

Its unconditional Theorem 1 proves exactly that the ratios are unbounded.

This rules out every finite limit, but does not distinguish between divergence

to $+\infty$ and oscillation with unbounded limsup.

(b, rigorous modulo Kovač–Luca Theorem 3) The paper proves full divergence

conditionally on either of the following:

1. for record indices $N$, meaning

$\tau(2^N-1)>\tau(2^m-1)$ for all \(m

\[ \frac{\tau(2^N+1)}{N}\longrightarrow\infty; \]

2. the bound

\[ \omega(\Phi_d(2))\leq 10\log d \]

for all but finitely many $d$.

(c, search-negative rather than a theorem) Searches for the exact title,

arXiv identifier, defining formula, and quoted doubling ratio found no later

primary paper claiming an unconditional resolution. This is an honest search

miss, not evidence that no such paper can exist. The authoritative live page

also still says OPEN, with no proof claim and no current worker.

2. New elementary observation: a uniform lower bound

Put

\[ A(k):=\tau(2^k-1),\qquad B(k):=\tau(2^k+1). \]

(a, elementary-rigorous) For every $k\geq1$,

\[ 2^{2k}-1=(2^k-1)(2^k+1) \]

and

\[ \gcd(2^k-1,2^k+1)=1. \]

The divisor function is multiplicative on coprime arguments, so

\[ A(2k)=A(k)B(k). \tag{1} \]

Since $2^k+1>1$, $B(k)\geq2$.

(a, elementary-rigorous) Splitting the first $2n$ indices into even and

odd indices and using (1) gives

\[ \begin{aligned} f(2n) &=\sum_{k\leq n}A(2k)+\sum_{k\leq n}A(2k-1)\\ &=\sum_{k\leq n}A(k)B(k)+\sum_{k\leq n}A(2k-1)\\ &>2\sum_{k\leq n}A(k)=2f(n). \end{aligned} \tag{2} \]

Therefore

\[ \boxed{\frac{f(2n)}{f(n)}>2\quad\text{for every }n\geq1.} \]

I did not find this point stated in Kovač–Luca v4. It does not settle the

limit, but it excludes small-ratio oscillation and is uniform, whereas the

known limsup theorem is subsequential.

3. A weighted dyadic-ray inequality

Write

\[ k=2^a r,\qquad r\ \text{odd}, \]

and define

\[ h(k):=\tau(r)-\mathbf 1_{\{a=0,\ 3\mid r\}}. \tag{3} \]

(b, rigorous modulo the Bang–Zsigmondy primitive-divisor theorem) For each

divisor $d\mid r$, set $m=2^{a+1}d$. Except when $m=6$, Bang–Zsigmondy

gives a primitive prime divisor $q_m$ of $2^m-1$. Its multiplicative order

is $m$. Since

\[ k=\frac m2\frac rd \]

and $r/d$ is odd,

\[ 2^k\equiv -1\pmod {q_m}; \]

hence $q_m\mid 2^k+1$. Primes belonging to different $m$'s are distinct,

because their orders are different. The exceptional value $m=6$ occurs

exactly once when $a=0$ and $d=3$. Consequently

\[ \omega(2^k+1)\geq h(k) \]

and therefore

\[ B(k)=\tau(2^k+1)\geq 2^{h(k)}. \tag{4} \]

Define the probability weights

\[ \mu_n(k):=\frac{A(k)}{f(n)}\qquad(1\leq k\leq n). \]

(b, rigorous modulo Bang–Zsigmondy) Equations (1) and (4) yield the

weighted inequality

\[ \boxed{\frac{f(2n)}{f(n)} >L(n):=\sum_{k\leq n}\mu_n(k)\,2^{h(k)}.} \tag{5} \]

Thus the doubling ratio is bounded below by an $A(k)$-weighted exponential

moment of the divisor count of the odd part of $k$.

(b, rigorous modulo Bang–Zsigmondy) A concrete sufficient lemma for the

open problem is now:

\[ \forall H\geq1,\qquad \frac{\sum_{\substack{k\leq n\\h(k)\leq H}}A(k)}{f(n)} \longrightarrow0. \tag{6} \]

Indeed, (6) implies

\[ L(n)\geq 2^{H+1}\mu_n\{k:h(k)>H\} =2^{H+1}(1-o(1)) \]

for every fixed $H$, and then $H\to\infty$ gives $L(n)\to\infty$.

This is a sufficient condition, not a proved fact and not a necessary

condition; no closure is claimed.

4. A fourfold lower bound with an explicit obstruction

(b, rigorous modulo Bang–Zsigmondy) Formula (4) has a particularly simple

consequence:

if $k$ is a power of $2$, then $B(k)\geq2$;
$B(3)=\tau(9)=3$;
for every other $k$, $h(k)\geq2$, so $B(k)\geq4$.

Let

\[ P(n):=\sum_{\substack{2^j\leq n\\j\geq0}}A(2^j). \]

Since $A(3)=\tau(7)=2$ and every odd-index term $A(2k-1)\geq1$,

(1) gives

\[ \boxed{f(2n)\geq 4f(n)-2P(n)-2\mathbf 1_{\{n\geq3\}}+n.} \tag{7} \]

(b, rigorous modulo Bang–Zsigmondy) In particular,

\[ P(n)=o(f(n)) \quad\Longrightarrow\quad \liminf_{n\to\infty}\frac{f(2n)}{f(n)}\geq4. \tag{8} \]

This isolates a small explicit obstruction to getting a uniform factor $4$

from the primitive-divisor method: possible concentration of the divisor mass

on the single dyadic ray $k=1,2,4,8,\ldots$. Even proving (8)'s hypothesis

does not prove divergence; the stronger mass-escape statement (6), or another

idea, is still needed.

5. Independent exact computation

The standalone checker is

erdos893_wave7s_reverify.py.

It does not read OEIS or FactorDB data. It:

1. factors every $\Phi_d(2)$ for $1\leq d\leq276$ with PARI/GP;

2. calls PARI's proof-producing isprime(p,1) on every returned factor;

3. independently recomputes each $\Phi_d(2)$ in Python from

\[ 2^d-1=\prod_{e\mid d}\Phi_e(2); \]

4. checks every factor product and reconstructs every $2^n-1$;

5. recomputes $A(n)$, $f(n)$, the ratios, and the lower bound (5).

Run:

python runs/erdos893_wave7s_reverify.py --max-n 138 --timeout 240

Environment used: Python 3.12.3, PARI/GP 2.15.4. The full run took 97.933

wall-seconds. A quick independent smoke test is

--max-n 32.

(d, computational-only) Checker SHA-256:

b6bf126a8125ef2837cd622621c9d2ba9be4880ed41335ed7feb3298cc80a733.

(d, computational-only) The checker proves all factorizations needed for

$A(n)$ through $n=276$, hence all exact ratios through $n=138$. Its

dyadic-block minima are:

| range of $n$ | exact minimum of $f(2n)/f(n)$ (where) | exact minimum of $L(n)$ (where) |

|---:|---:|---:|

| $1$–$2$ | $3$ ($n=1$) | $2$ ($n=1$) |

| $3$–$4$ | $3$ ($n=4$) | $2$ ($n=3$) |

| $5$–$8$ | $39/11$ ($n=5$) | $26/11$ ($n=5$) |

| $9$–$16$ | $135/31$ ($n=9$) | $90/31$ ($n=9$) |

| $17$–$32$ | $563/103$ ($n=17$) | $378/103$ ($n=17$) |

| $33$–$64$ | $18689/1311$ ($n=40$) | $3610/563$ ($n=34$) |

| $65$–$128$ | $151011/8165$ ($n=65$) | $192834/18689$ ($n=80$) |

| $129$–$138$ | $26842135/175631$ ($n=134$) | $3162522/175631$ ($n=134$) |

(d, computational-only) Over the whole certified range $1\leq n\leq138$,

the minimum ratio is exactly $3$, attained precisely at $n=1,2,4$, and the

maximum is

\[ \frac{2427325}{11077}\approx219.131985 \]

at $n=90$. At the endpoint,

\[ \frac{f(276)}{f(138)} =\frac{28283039}{178579}\approx158.378303, \qquad L(138)=\frac{3305898}{178579}\approx18.512244. \]

This computation is an independent certificate, not a range extension over

Kovač–Luca's database-assisted exact data through ratio index $603$.

6. Exact wall

(d, current computational observation) Kovač–Luca's exact table uses

$\tau(2^n-1)$ through $n=1206$, giving exact ratios through $n=603$.

The next consecutive term is not merely an arbitrary omitted value:

the current factorization record for $2^{1207}-1$

contains a still-composite 337-decimal-digit (1120-bit) cofactor. The

Cunningham Project

and current factor databases therefore do not supply the exact value of

$\tau(2^{1207}-1)$. An exact consecutive extension to ratio $n=604$

requires resolving that cofactor (or otherwise determining its prime

multiplicity pattern).

(c, cost estimate only) This is a distributed special-number-field-sieve

project, not a few-minute local calculation. For scale, the primary report

“Factorization of a 1061-bit number by the Special Number Field Sieve”

records a campaign of hundreds of CPU-years for a slightly smaller Mersenne

number. A planning estimate for the 1120-bit C337 target is therefore on the

order of $10^5$–$10^6$ modern core-hours, plus a high-memory parallel

linear-algebra stage—roughly \$4,000–\$40,000 at \$0.04/core-hour, with no

guarantee because the unknown factor sizes matter. I did not run such a job.

7. Honest conclusion

(a) The new unconditional elementary result is the uniform bound

$f(2n)/f(n)>2$.

(b, modulo Bang–Zsigmondy) The stronger weighted inequality (5), the

explicit fourfold obstruction (7), and the sufficient mass-escape lemma (6)

are rigorous.

(d) Exact from-scratch factor/primality certificates verify every ratio

through $n=138$, including the table above.

(c) None of these supplies the required uniform mass-escape estimate.

The precise missing input for this route is (6), or some weaker estimate that

still forces its weighted exponential moment in (5) to infinity. Present

standard primitive-divisor machinery supplies many factors termwise but does

not control where the highly irregular weights $A(k)=\tau(2^k-1)$ concentrate.

Thus the original problem remains open.

PARTIAL: proved the uniform bound f(2n)/f(n)>2 and a Bang–Zsigmondy weighted reduction, with an independent exact certificate through n=138; full divergence remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger