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

Question

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 [further warning: $2^{104}+9262111$ is prime; $9262111$ should be replaced by $1517871$] ]. If it is prime infinitely often we probably can't prove it -- but should we be conjecturing it?

Answer 1

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