It occurs to me that it would be very cool if for a prime $p_1$ we have $p_{2}=2^{p_1}-1$ prime, and then $p_3 = 2^{p_2}-1$ prime, and so on. This would be a sort of infinite sequence of Mersenne primes. I know this particular case isn't known, as it isn't known if there are an infinite number of Mersenne primes to begin with.

So my question is as in the title. Does there exists a function $f$ such that for some prime $p_1$, $p_{n+1}=f(p_n)$ gives a sequence of primes? Either $f$ must grow incredibly fast, as otherwise that'd make computing large primes easy, or perhaps there is an $f$ and merely the existence of some $p_1$ proven. Both of these possibilities seem plausible to me, so I'm wondering if there is a result like this.

Preferably $f: N \to N$ as some sort of expression in $Z[t]$ with exponentials, but if there are none, what about something more algorithmic such as computing gcd's or largest factors? I.e., prime in, prime out. I mean, obviously there is an algorithm for computing primes in sequence, but I'm thinking some more clean.

  • $\begingroup$ It is known that any polynomial $f$ can give just primes for $f(n)$. Your question is similar in something to this denied fact. Anyway, the only thing I see clearly is that f should be irreducible. $\endgroup$ – Piquito Jan 20 '16 at 16:12
  • $\begingroup$ Many such functions exist. Finding an explicit formula for any of them is a different mater. $\endgroup$ – Julián Aguirre Jan 20 '16 at 17:54
  • 2
    $\begingroup$ You probably want to require that $f(n) \gt n$, or alternatively that the primes in the sequence are distinct, otherwise any $f$ with $f(2) = 3$ and $f(3) = 2$ is a solution. $\endgroup$ – Dan Brumleve Jan 21 '16 at 0:38

There is no known provably-correct way to find a prime larger than $n$ in $O((\log{n})^k)$ time (although this can be done by simply counting up from $n$ and testing with AKS if Cramér's conjecture holds), so unless we solve that open problem we won't be able to find such a function that is easy to compute. The particular example you mention has been studied, it is called the Catalan-Mersenne number conjecture.


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.