# Mersenne Prime Sequences

Hi.

Given the following sequence (of Mersenne primes):

$A_{1} = 2$

$A_{n} = 2^{A_{n-1}} - 1$

The first five elements are all prime numbers:

$2$

$2^{2}-1=3$

$2^{3}-1=7$

$2^{7}-1=127$

$2^{127}-1=170141183460469231731687303715884105727$

As far as my memory serves, it has been conjectured that this sequence contains ONLY prime numbers.

Sadly, calculating the sixth element (let alone proving it's a prime number or providing a counterexample) appears computationally infeasible, so I guess that this remains an open conjecture.

My question is with regards to a similar type of sequences:

$B_{n} = 2^{B_{n-1}} - 1$

Where $B_{1}$ is a Mersenne prime which is NOT in $A_{n}$

Has it been conjectured that ANY such sequence will ALWAYS contain a composite number?

Thanks

• The Wagstaff heuristics primes.utm.edu/mersenne/heuristic.html assert that for large prime $p$, the probability of $2^p-1$ being prime is about $(\log p)/p$ (up to some multiplicative constant). So it seems unlike to me that $A_n$ contains only prime numbers. I would rather conjecture that any such sequence will contain a composite number. – François Brunault Jun 15 '13 at 19:00
• Yes, for a discussion see also en.wikipedia.org/wiki/Double_Mersenne_number. Whether Catalan really conjectured that all of $A_n$ are prime is not clear to me. – Dietrich Burde Jun 15 '13 at 19:03
• Thank you Francois! $2^{p}-1$ is a Mersenne number. I think that the probability of a Mersenne number to be in $A{n}$ is smaller than the probability of a Mersenne number to be a prime. So if I'm correct, then your probabilistic argument cannot be used in order to conclude that it is unlikely for $A{n}$ to contain only prime numbers. – barak manos Jun 15 '13 at 19:27
• Based on the heuristics mentioned by Francois, it seems rather reasonable to conjecture that $A_n$ is composite for all $n \geq 6$. – Stefan Kohl Jun 15 '13 at 19:32
• @Barakman : The point is that there is no obvious bias towards primality arising from belonging to $A_n$. The exponents of the numbers in $A_n$ are very large, and I see no reason why they should be more prime than the Mersenne numbers of comparable size. So their primality becomes soon unlikely. – François Brunault Jun 15 '13 at 19:38

## 2 Answers

Remark: I'm composing my two comments at the OP making them an answer

Mersenne-numbers and iterated Mersenne-numbers of the same size have the significant difference, that the iterated ones cannot have "small" prime-factors while for the basic Mersenne numbers there is no such restriction. For instance a two-time iterated Mersenne number cannot have primefactors $3,5,11,...$ and only $7,23,..$ can be primefactors of such a number. So the possible number-of-primefactors for highly iterated Mersenne-numbers is much smaller than a naive expectation based on that for non-iterated Mersenne-numbers of the same size.

This looks even more drastical for higher iterates. Let's denote $n_0$ a variable having any positive integer value, $n_1=2^{n_0}−1,$, $n_2=2^{n_1}−1$ and so on. Then any $n_4$ can have at most two of the primes below $10,000$ as factors, namely $2879$ and $4703$ (or: at most $5$ of the primes below $100,000$ can be factors, or at most $21$ of the primes below $1,000,000$) and the likelihood of being prime for some $n_4$, based on the required subsequent statistical considerations only, should be much larger than that of a non-iterated Mersennenumber $n_1$ of the same size.

Appended: for any $n_5$ we have only $3$ primes below $1,000,000$ as possible primefactors, namely $214559$,$429119$ and $858239$

Iterated sequences have finite number of primes, it have been proved for elliptic sequence, and polynomial maps, see the works of Graham and company on elliptic curve, and a student of Silverman wrote a thesis on this, it is on the arxiv.

• Welcome to MO! Could you perhaps provide some more details. (You can expand the answer via clicking 'edit' just below it.) – user9072 Jun 17 '13 at 16:34
• Euclid proved the opposite, for a certain iterated sequence, and thus for infinitely many other iterated sequences. Later Dirichlet improved upon this by showing it held for every possible permissible instance of the iterated sequence. Gerhard "Is Talking About Iterated Adding" Paseman, 2013.06.17 – Gerhard Paseman Jun 17 '13 at 16:53
• I think that alias is overstating what's been proven. There are certain elliptic divisibility sequences and certain polynomial orbits for which one can prove there are only finitely many primes. Some of these, in particular the ones that Graham Everest and his colleagues/students studied, can be somewhat subtle to prove; but roughly speaking, they all come from cases where there is a "map" from some other sequence that provides a nontrivial divisor. Of course, there are also trivial examples. But in general, it is only conjectured that EDS and poly orbits have finitely many primes. – Joe Silverman Jun 17 '13 at 18:35
• @JoeSilverman : but here it is an exponential iterated sequence, is there any reason to think that $\displaystyle 2^{\textstyle 2^{127}-1}-1$ is not prime and that there are not an infinity of primes when continuing the sequence ? – reuns May 13 '16 at 0:08
• @user1952009 Let $a_n$ be a sequence of positive integers whose entries don't have any particular reason to be composite, for example the sequence you suggest $2^{2^n}-1$. The "probability" that $a_n$ is prime is roughly $1/\log a_n$, so a rough heuristic is that if $\sum_{n=1}^\infty \frac{1}{\log a_n}$ converges, then the sequence contains finitely many primes, and if it diverges, then the sequence contains infinitely many primes. N.B. This is just a very coarse heuristic, it generally needs to be refined to take account of congruence conditions. But since you ask for a reason, there is it. – Joe Silverman May 13 '16 at 0:16