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<d<n$, then $2^d-1 \mid p$, where $1<2^d-1<p$, 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<M$. 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – reuns Feb 3 '19 at 11:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Feb 3 '19 at 11:11
  • $\begingroup$ @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. $\endgroup$ – Haran Feb 3 '19 at 11:19
  • $\begingroup$ 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. $\endgroup$ – Peter Feb 3 '19 at 11:23
  • 1
    $\begingroup$ 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. $\endgroup$ – user645636 Mar 3 '19 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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