Catalan-Mersenne Conjecture

The Catalan--Mersenne Iteration

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Set $C_0=2$ and recursively $C_{n+1}=2^{C_n}-1$ for integers $n\geq0$. A composite number is an integer greater than one with a proper divisor greater than one. The displayed target concerns every index $n>4$, using this exact zero-based convention; no different indexing of the initial term is substituted. [S1] [S2]

Statement recorded in the supplied source.

Are all Catalan-Mersenne numbers $C_n$ composite for $n > 4$? Here $C_0 = 2$ and $C_{n+1} = 2^{C_n} - 1$. [S1]

Short English statement

After the specified early terms, must every number in the iterated Mersenne construction be composite?

Research attempt

The precise target and indexing.

This attempt follows the catalogue's specific assertion: every $C_n$ with $n>4$ is composite, with $C_0=2$. It does not substitute another historical formulation about the sequence. Direct recursion gives \[ C_0=2,\quad C_1=3,\quad C_2=7,\quad C_3=127,\quad C_4=P=2^{127}-1, \] where \[ P=170141183460469231731687303715884105727. \] The next term is $C_5=2^P-1$, which is stored symbolically throughout. The Mersenne arithmetic and Lucas--Lehmer criterion documented by the GIMPS project [E1] were inspected on 1 October 2026. No claim about a current global factor-search record is needed in this attempt.

Compositeness propagates, making the target one question.

For integers $a,b>1$, \[ 2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+\cdots+2^{(b-1)a}). \] Both factors are greater than one. Thus if $C_j$ is composite, so is $C_{j+1}$, and then every subsequent term by induction. It follows that the catalogue assertion is equivalent to the single statement \[ C_5\text{ is composite}. \] One implication specializes to $n=5$; the other is the displayed factorization iterated. Proving some later term composite is insufficient: it leaves $C_5$ and possibly several further terms undecided. Conversely, a proof that $C_5$ is prime would disprove this exact catalogue target, even if a later term were composite. This distinction avoids an indexing shift in what must actually be settled.

Certifying the exponent without constructing the next term.

The Lucas--Lehmer theorem for prime exponent $p>2$ says that $2^p-1$ is prime exactly when the sequence \[ s_0=4,\qquad s_{j+1}=s_j^2-2\pmod{2^p-1} \] has $s_{p-2}=0$. Using this standard criterion [E1], the script executes the $125$ iterations for $p=127$, obtaining residue zero. The exponent $127$ is prime by trial division by $2,3,5,7,11$. Thus $P$ is prime. The criterion itself is cited rather than reproved; the modular arithmetic instance is actually executed. This certificate concerns $C_4$, not $C_5$. Running the corresponding criterion on $C_5$ would involve $P-2$ iterations on numbers with about $P$ bits, a wholly different computation.

The exact shape of every possible prime divisor.

Let $q$ be a prime divisor of $2^P-1$. It is odd, and the multiplicative order of two modulo $q$ divides the prime $P$. That order cannot be one, since no prime divides $2-1$. Hence it is exactly $P$, so $P\mid q-1$. Since $P$ and $q$ are odd, there is an integer $k\ge1$ with \[ q=2kP+1. \] In particular a factor is already at least $2P+1$, even though the number being factored is vastly larger still. Furthermore $2^{(q-1)/2}=2^{kP}\equiv1\pmod q$; Euler's criterion and the supplementary law for the quadratic character of two imply $q\equiv1$ or $7\pmod8$. Since $P\equiv7\pmod8$, this restricts $k$ to $0$ or $1\pmod4$. The residue restriction is a standard Mersenne factor sieve also described in [E1]; the first order argument already suffices for the complete candidate form.

These conditions do not imply that any candidate divides $C_5$. In the opposite direction, any proper integer divisor, even a composite one, would certify compositeness if its divisibility were proved. A factor search need not prove every candidate prime before trying its modular remainder.

A feasible exact factor test.

For a specified $q$, binary modular exponentiation evaluates $2^P\bmod q$ using only the $127$-bit exponent $P$. A residue of one would show $q\mid C_5$. Thus trying a moderate list of candidate factors is feasible even though writing down $C_5$ is not. The script tests all integers $q=2kP+1$ for $1\le k\le10000$, without a probable-prime filter and without omitting either residue class. None divides $C_5$. Because every prime factor has this form, this also excludes every prime divisor $q\le20000P+1$. This lower bound on a possible factor is conditional only on the cited Lucas--Lehmer theorem and the executed exact arithmetic, not on a probabilistic primality test for the candidate $q$.

There is no resulting lower bound comparable to $\sqrt{C_5}$. To prove primality by trial division would require eliminating every prime divisor through that square root, whereas our upper candidate is linear in $P$ and the square root is exponential in $P$. Conversely, a failure to find a factor supplies no evidence strong enough to assert compositeness. A heuristic expectation that a randomly chosen large integer is usually composite has no force for this individual number.

The circular route through an exponent factor.

One might hope to use the factorization $2^{ab}-1$ at the first unresolved step. Its exponent here is $P$, already certified prime, so that mechanism is unavailable. It becomes effective only after a composite term has been found. Invoking it to establish the first composite term would therefore assume the very input it needs. Likewise, a formal factorization over complex roots of unity does not give nontrivial integer factors when the exponent is prime.

Reproducibility, remaining gap, and outcome.

The exponent certificate and factor scan are stored in checks.py and results.json at _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. The decisive unresolved step is a compositeness certificate for $2^P-1$, for example one nontrivial divisor, or a primality certificate that would refute the stated assertion. Neither was obtained. Outcome: UNRESOLVED. The infinite tail was reduced exactly to its first term, and a finite candidate-factor interval was excluded; the reduction and the finite scan are not a solution of that term.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1119 (NT-016), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Double Mersenne number overview. https://en.wikipedia.org/wiki/Double_Mersenne_number. Bibliographic information from the supplied record.

• E1 Great Internet Mersenne Prime Search, Mathematics and Research Strategy, sections on trial factoring and Lucas--Lehmer primality testing. https://www.mersenne.org/various/math.php. Project documentation inspected 1 October 2026. Used for the standard Lucas--Lehmer criterion and Mersenne factor restrictions, not for a claim about a completed primality test of $C_5$.