Density and liminf of $h(n)$, least $l$ making $2^n\!-\!1,\ldots,l^n\!-\!1$ pairwise coprime (Erdős #770)
Statement
For a positive integer $n$, let $h(n)$ be the least integer $l$ such that $2^n-1,\,3^n-1,\,\ldots,\,l^n-1$ are mutually coprime (the listed values are pairwise coprime). Erdős asked three linked questions: (i) does the density $\delta_p$ of the set of integers $n$ with $h(n)=p$ exist for every prime $p$; (ii) is $\liminf_{n\to\infty}h(n)=\infty$; and (iii) is it true that if $p$ is the greatest prime with $p-1\mid n$ and $p>n^{\epsilon}$, then $h(n)=p$?
Acceptance. FULLY RESOLVES: complete proofs (Lean/Coq preferred, else full written) settling the stated questions — establishing existence or non-existence of each density $\delta_p$, deciding whether $\liminf h(n)=\infty$, and proving or refuting the characterisation ('$p$ greatest prime with $p-1\mid n$ and $p>n^{\epsilon}$ $\Rightarrow h(n)=p$'). A definitive proof of any one of the three named sub-questions resolves that sub-question. ADVANCES: prove $h(n)=3$ for infinitely many $n$ (equivalently $\gcd(2^n-1,3^n-1)=1$ infinitely often); prove a nontrivial lower bound on the density of $\{n:h(n)=p\}$ for some fixed prime $p$; or a reproducible computation extending the tabulated values of $h(n)$ and of $\{n:h(n)=3\}$ (OEIS A263647) to a new certified range, with the search code and the observed density statistics. Deliver the proof(s), or the computation code plus certified extended tables and density estimates.
Background
A problem of Erdős [Er74b]; listed as open on erdosproblems.com/770 (fetched 2026-07-21, status 'open'). Elementary facts: $h(n)=n+1$ exactly when $n+1$ is prime, and $h(n)$ is unbounded along the odd integers $n$; it is expected (but open) that $h(n)=3$ — i.e. $\gcd(2^n-1,3^n-1)=1$ — for infinitely many $n$. This is the coprimality-of-$k^n-1$ companion to Erdős #820 (erdosproblems.com/820), which studies the closely related function $H(n)$ (the least $l$ admitting some $k<l$ with $\gcd(k^n-1,l^n-1)=1$) and its extreme growth; the integers $n$ with $\gcd(2^n-1,3^n-1)=1$ form OEIS A263647. A Lean formalisation of the statement exists in the formal-conjectures project. No prize. Attacker's tool: direct computation of $h(n)$ over long ranges (gcds of $k^n-1$ via cyclotomic structure and Bang–Zsygmondy primitive-prime-divisor theory) to tabulate the value distribution, estimate the densities $\delta_p$, test whether $\liminf h(n)=\infty$, and check the $p-1\mid n$ characterisation empirically before an analytic attack.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #770 (T. F. Bloom) | website |
| REF-02 | OEIS A263647 — n with gcd(2^n-1, 3^n-1) = 1 | website |
| REF-03 | Erdős Problem #820 (T. F. Bloom) — companion growth problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.