0
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$
    – François Brunault
    Commented Jun 15, 2013 at 19:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dietrich Burde
    Commented Jun 15, 2013 at 19:03
  • $\begingroup$ 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. $\endgroup$
    – barak manos
    Commented Jun 15, 2013 at 19:27
  • 1
    $\begingroup$ Based on the heuristics mentioned by Francois, it seems rather reasonable to conjecture that $A_n$ is composite for all $n \geq 6$. $\endgroup$
    – Stefan Kohl ♦
    Commented Jun 15, 2013 at 19:32
  • $\begingroup$ @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. $\endgroup$
    – François Brunault
    Commented Jun 15, 2013 at 19:38

2 Answers 2

Reset to default
2
$\begingroup$

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$

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Welcome to MO! Could you perhaps provide some more details. (You can expand the answer via clicking 'edit' just below it.) $\endgroup$
    – user9072
    Commented Jun 17, 2013 at 16:34
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jun 17, 2013 at 16:53
  • 4
    $\begingroup$ 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. $\endgroup$
    – Joe Silverman
    Commented Jun 17, 2013 at 18:35
  • $\begingroup$ @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 ? $\endgroup$
    – reuns
    Commented May 13, 2016 at 0:08
  • $\begingroup$ @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. $\endgroup$
    – Joe Silverman
    Commented May 13, 2016 at 0:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .