Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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
1  
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
show 3 more comments

1 Answer 1

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|improve this answer
    
Welcome to MO! Could you perhaps provide some more details. (You can expand the answer via clicking 'edit' just below it.) –  quid Jun 17 '13 at 16:34
1  
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
2  
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
add comment

Your Answer

 
discard

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.