# When are there infinitely many primes in a sequence generated by a simple recurrence relation?

tl;dr summary: am I right in thinking that we expect $2^n-1$ to be prime infinitely often, but $2^n+1$ to be prime only finitely often? What's the general story here?

An applied mathematician asked me a question about whether there were infinitely many primes in a certain sequence generated by a linear recurrence relation, and I was quick to respond "if there is not a trick to show that there are only finitely many using elementary methods, then there will probably be infinitely many but we probably won't be able to prove it". Too quick, I suspect.

Here is a general, but vague, question that I realise I don't understand properly. If $a,b,c$ are integers, with $a>1$ and $c>0$, and if the sequence $x_n=\frac{a^n+b}{c}$ ($n=1,2,3,\ldots$) is a sequence of positive integers, when do we expect this sequence to contain infinitely many primes?

There are two tricks I know.

There's a trivial trick "there exists a prime $p$ such that $x_n$ is always a multiple of $p$" which tells me e.g. that the sequence $3^n-1$ only contains finitely many primes.

There's a slightly more subtle trick which tells me that $\frac{4^n-1}{3}$ only contains finitely many primes, and this is that $4^n-1=(2^n+1)(2^n-1)$ which will prove that $\frac{4^n-1}{3}$ is composite when $n$ is large enough. And that's all I know.

I've seen the covering congruences trick used by Graham (R. L. Graham, A Fibonacci-like sequence of composite numbers) to prove that there are general recurrence relations that contain no primes for slightly less obvious reasons, but I'm not sure if I can get this to work in my case. (edit Thanks to user102986, who reminded me of a covering congruence argument which was posted to this site 7 years ago in response to a question of mine which I'd completely forgotten about -- see comments below).

I initially suspected that if none of these tricks worked then perhaps there would be infinitely many primes but that we couldn't prove this; however this article by Kent Boklan and John Conway adds more meat to the suggestion, probably long believed, that there are only finitely many Fermat primes and hence only finitely many primes of the form $2^n+1$. Conversely GIMPS (motto: "$2^p-1$ may be prime"!) seems to be producing a steady stream of Mersenne primes. There are standard proofs that if $2^n+1$ is prime then $n$ is a power of 2, and that if $2^n-1$ is prime then $n$ is prime, and there are more primes than powers of 2, but this is a little simplistic in my mind and I suspect that people have a better understanding of what is, or should be, going on nowadays. My idle question: what is the general picture?

edit: in response to user102986's comments to make my question more precise, I will ask a random specific question.

Q) Is $2^n+2017$ is prime infinitely often? [warning: $2^n+9262111$ is never prime -- see link in the comments to a 2009 question of mine]. If it is prime infinitely often we probably can't prove it -- but should we be conjecturing it?

• You can also interlace two or more sequences so have $3^k-1$ for $n=2k$ and $(4^k-1)/3$ for $n=2k-1.$ – Aaron Meyerowitz Dec 29 '16 at 16:35
• You might like to look at some of the answers to Buzzard's question here: mathoverflow.net/questions/5323/… (Why does $2^n+9262111$ not qualify as a covering congruence argument which applies in your case?) More seriously, in order to avoid a repeat of the low quality answers to that question, perhaps you can make your question more precise and ask what you really want to know, which seems to be something like "is there a known and accepted way to make conjectures about these questions which avoids all the pitfalls I just mentioned ( – user102986 Dec 29 '16 at 16:38
• (and maybe others I don't know about)." – user102986 Dec 29 '16 at 16:38
• Thanks user102986. I had completely forgotten about my previous question; it absolutely qualifies as a covering congruence argument. I am not sure I can make my question more precise; I was just idly observing that I didn't understand the dichotomy on a conceptual level. – Kevin Buzzard Dec 29 '16 at 18:05

Am I right in thinking that we expect $2^n - 1$ to be prime infinitely often, but $2^n+1$ to be prime only finitely often? What's the general story here?

Yes, you are. The (simplest) reasons for those conjectures come from the Borel-Cantelli Lemmas, the Prime Number Theorem, and the basic divisibility properties of $2^n - 1$ and $2^n + 1$.

• The first Borel-Cantelli Lemma says that if $E_1, E_2, \ldots$ is a sequence of events then $$\sum_{n} \operatorname{Pr}[E_n] < +\infty$$ implies that $$\operatorname{Pr}[\text{infinitely many } E_n \text{ occur}] = 0,$$ while the second Borel-Cantelli Lemma says that is $E_1,E_2, \ldots$ are independent and $$\sum_{n} \operatorname{Pr}[E_n] = +\infty$$ then $$\operatorname{Pr}[\text{infinitely many } E_n \text{ occur}] = 1.$$

• The Prime Number Theorem tell us that, in some very imprecise sense, the "probability" that $N$ is a prime number is $\approx 1 / \log N$.

• It is easy to prove that $2^n - 1$ is prime only if $n$ is prime, while $2^n + 1$ is prime only if $n$ is a power of two.

In conclusion, the heuristic are the following: There should be infinitely many Mersenne primes, since $$\sum_{p \text{ prime}} \frac1{\log(2^p - 1)} \approx \sum_{p \text{ prime}} \frac1{p \log 2} = + \infty ,$$ while there should be only finitely many Fermat primes, since $$\sum_{k = 1}^{+\infty} \frac1{\log(2^{2^k} - 1)} \approx \sum_{k = 1}^{+\infty} \frac1{2^k \log 2} < + \infty .$$

• Right, but this involves the insight that one can greatly cut down on the possibilities for $n$ for which $2^n+1$ can be prime. I learnt in 2009 (and again today) that $2^n+9262111$ is only prime finitely often but I can't see how to make your heuristics apply here. – Kevin Buzzard Dec 29 '16 at 18:07