# Nested Mersenne Primes

A Mersenne Prime is any prime number of the form $$2^n-1$$, where $$n$$ is a positive integer. We can trivially see that for any Mersenne Prime $$p=2^n-1$$, $$n$$ has to be prime, as if $$d \mid n$$ and $$1, then $$2^d-1 \mid p$$, where $$1<2^d-1, contradicting the fact that $$p$$ is prime.

However, it is not necessary that any prime $$n$$ would generate a prime $$2^n-1$$. The first example of this would be $$2^{11}-1=2047=23\cdot89$$. In fact, as we make $$n$$ higher, the fraction of Mersenne numbers which are prime, reduces quickly.

Note that: $$2^2-1=3 \space; 2^3-1=7 \space; 2^7-1=127 \space; 2^{127}-1=170141183460...715884105727$$ Thus, if we define the set $$\mathbb P$$ to be the set of all primes, then: $$2,2^2-1,2^{2^2-1}-1,2^{2^{2^2-1}-1}-1 \in \mathbb P$$ Question: Define the sequence $$(a_i)$$ for $$i \in \mathbb N$$ to be as follows:

$$(i)$$ $$a_1 = p \in \mathbb N$$

$$(ii)$$ $$a_{n+1} = 2^{a_n}-1 \space \forall \space n \in \mathbb N$$

Does there exist any $$p$$ such that $$(a_i)$$ consists only of primes?

It seems unlikely that there exists any such $$p$$. However, I am not able to disprove this since each time, the power is replaced by a prime, restricting me from using any modulo prime method.

P.S. Assume $$n=ab$$ where $$a,b>1$$. Then, $$M=2^n-1=(2^{a})^b-1 \implies 2^a-1 \mid M$$ Now, since $$a>1 \implies 2^a-1>1$$. Moreover, $$b>1 \implies 2^a-1. Thus, $$M$$ has a factor other that $$1$$ and $$M$$ which shows that $$M$$ is not prime. Thus, for $$M$$ to be a Mersenne Prime, $$n$$ has to be prime. @Jossie Caldaron I request you to refrain from downvoting posts without full knowledge of concept and I also ask you to give OPs the benefit of doubt. I had already posted why $$n$$ must be prime, so please request clarification from now onward.

• The random model for the primes, which predicts quite well the distribution of Mersenne primes (taking in account their divisors are of the form $2kp+1$) says no, there is no such sequence. Otherwise this is unknown as most recursive problems with primes. Commented Feb 3, 2019 at 11:11
• Deciding this question is almost surely out of reach. Incredibly, we do not even know whether there are infinite many primes $p$ , such that $2^p-1$ is composite. I agree that it is extremely unlikely, that such a $p$ exists , considering the quickly growing function. Commented Feb 3, 2019 at 11:11
• @Peter Is that a well established conjecture? If it is, then we cannot answer this problem unless we prove the infinitude of Mersenne primes or this conjecture. Commented Feb 3, 2019 at 11:19
• It is , of course , NOT conjectured that only finite many primes $p$ exist such that $2^p-1$ is composite. The point is that we cannot rule it out. Commented Feb 3, 2019 at 11:23
• Also relates to the polynomial $2x^2+4x+1$ as all entries except $2$ and $2^2-1$ are on the iteration of this polynomial.
– user645636
Commented Mar 3, 2019 at 3:06

As someone who started out posting on mersenneforum about 9 or 10 years ago (starting with the related conjecture, only recently gave up), Here's a few things I know:

$$2x^2+4x+1\land x=2^p+1 \to 2^{2p+1}-1$$

aka if p is prime, this function Iterated follows a Cunningham chain of first kind in the exponents.

This relates because mersenne prime exponents, can only happen to be certain places in a cunningham chain, namely at the beginning or end (or both if of length 1):

a second fact via the Prime Glossary:

Note that some authors extend the definition of Cunningham Chain to all sequences of primes pi the form pi+1 = api+b where a and b are fixed, relatively prime integers with a > 1.

So your sequence ( arguably any sequence), can be modeled as composition of generalized cunningham chains, on top of each other, because $$2^p-1=2kp+1$$ for some k if p is prime.

I could add more, but not directly related to this question, which is likely out of reach even with $$(2^p-1)^{2n}\equiv 2^{n(p-1)}\bmod{2^{p+1}-1}$$