# 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

@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 ? – user1952009 May 13 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 at 0:16