MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?


share|cite|improve this question
The Wagstaff heuristics 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 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

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.

share|cite|improve this answer
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 ? – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.