A Mersenne prime is a prime number of the form $2^p-1$ where $p$ has to be a prime number. Now, let $p_0$ be a prime number, and let us define the sequence $p_n = 2^{p_{n-1}}-1$. Is there a $p_0$ such that the sequence $p_n$ is a sequence of primes ? I checked it for the first 4 terms (starting with $p_0 = 2$) and it looks like it works. Obviously I'm sure it fails at some point for such simple case, but is there a $p_0$ such that this sequence is a sequence of prime numbers ?

Edit: Funny, it works for the 5 first terms starting at $p_0 = 2$

In particular, $p_{n+1} = p_n + \sum_{k = p_{n-1}}^{p_{n} - 1} 2^k$

Another fun formula is $p_{n+1} +1 = (p_n +1) 2^{p_n - p_{n-1}}$, or simply $\prod_{k=1}^n (1+p_k) = 2^{\sum_{k=0}^{n-1} p_k}$, that is, $\sum_{k=0}^{n-1} p_k = \sum_{k=1}^n ln(1+ p_k)/ln(2)$. You have so many of them because $1+p_{n+1} = 2^{p_n}$ and $p_{n+1} = \sum_{k=0}^{p_n-1} 2^{k}$ :<

  • $\begingroup$ It is not known if/that there are infinitely many Mersenne primes so such a sequecne is definitely not known. It might be possible to give an argument why it cannot exist. But I do not know one. $\endgroup$
    – quid
    Nov 11 '14 at 23:43
  • 2
    $\begingroup$ Mathematica 10.0.1 confirms $p_5 = 170141183460469231731687303715884105727$ to be prime, but overflows on the computation of $p_6 = 2^{p_5}-1$, FYI my \$MaxNumber is ~$10^{1355718576299609}$ wich is a lot more than what the documentation presents as usual max. $\endgroup$
    – AlexR
    Nov 11 '14 at 23:52
  • $\begingroup$ It's funny, if one takes $p_0 = 5$, then $p_1$ is also prime $\endgroup$
    – sure
    Nov 12 '14 at 1:00

Congratulations. You've just re-invented the Catalan-Mersenne sequence:


The first five elements are, indeed, prime. Is the next number in this sequence prime? Nobody knows, because the 6th number is far too large for any known primality test (it has about $5 \times 10^{37}$ digits).

At any rate, this is the only known candidate for such an infinite sequence. There is only one additional known Mersenne prime whose exponent is also a Mersenne: $2^{31}-1=2147483647$ (with $31=2^{5}-1$), so you might be tempted to try starting a similar sequence with $5$:


Unfortantely, the next number is $2^{2147483647}-1$, which is known to be composite (it has a surprisingly small factor: $295,257,526,626,031$).


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.