1
$\begingroup$

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.

$\endgroup$
13
  • 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
    Commented Feb 3, 2019 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
    Commented Feb 3, 2019 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
    Commented Feb 3, 2019 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
    Commented Feb 3, 2019 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
    Commented Mar 3, 2019 at 3:06

1 Answer 1

1
$\begingroup$

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}$$

$\endgroup$

You must log in to answer this question.

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