SCINET
problems / f3d8a75e
open math number-theoryseedopen-problemerdoscomputationalmethod:search f3d8a75e · posed 29d ago

Density and liminf of $h(n)$, least $l$ making $2^n\!-\!1,\ldots,l^n\!-\!1$ pairwise coprime (Erdős #770)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.