Infinitely many primes of the form $2^n+c$ as $n$ varies?

Question

At the time of writing, question 5191 is closed with the accusation of homework. But I don't have a clue about what is going on in that question (other than part 3) [Edit: Anton's comments at 5191 clarify at least some of the things going on and are well worth reading] [Edit: FC's excellent answers shows that my lack of clueness is merely due to ignorance on my own part] so I'll ask a related one.

My impression is that it's generally believed that there are infinitely many Mersenne primes, that is, primes of the form $2^n-1$. My impression is also that it's suspected that there are only finitely many Fermat primes, that is, primes of the form $2^n+1$ (a heuristic argument is on the wikipedia page for Fermat primes). [EDIT: on the Wikipedia page there is also a heuristic argument that there are infinitely many Fermat primes!]

So I'm going to basically re-ask some parts of Q5191, because I don't know how to ask that a question be re-opened in any other way, plus some generalisations.

1) For which odd integers $c$ is it generally conjectured that there are infinitely many primes of the form $2^n+c$? For which $c$ is it generally conjectured that there are only finitely many? For which $c$ don't we have a clue what to conjecture? [Edit: FC has shown us that there will be loads of $c$'s for which $2^n+c$ is (provably) prime only finitely often. Do we still only have one $c$ (namely $c=-1$) for which it's generally believed that $2^n+c$ is prime infinitely often?]

2) Are there any odd $c$ for which it is a sensible conjecture that there are infinitely many $n$ such that $2^n+c$ and $2^{n+1}+c$ are simultaneously prime? Same question for "finitely many $n$".

3) Are there any pairs $c,d$ of odd integers for which it's a sensible conjecture that $2^n+c$ and $2^n+d$ are simultaneously prime infinitely often? Same for "finitely often".

Answer 1

Buzzard is correct to be skeptical of the most naive arguments: Erdos observed that $2^n + 9262111$ is never prime.

[edit Jan 2017 by Buzzard: the 9262111 has sat here for 7 years but there's a slip in Pomerance's slides where he calculates the CRT solution. The correct conclusion from Pomerance's arguments is that $2^n+1518781$ is never prime. Thanks to Robert Israel for pointing out that $2^{104}+9262111$ is prime.]

Question one is an incredibly classical problem, of course. Observe that the proof that $2^n + 3$ and $2^n + 5$ are both prime finitely often can plausibly work for a single expression $2^n + c$ for certain $c$. It suffices to find a finite set of pairs $(a,p)$ where $p$ are distinct primes such that every integer is congruent to $a$ modulo $p - 1$ for at least one pair $(a,p)$. Then take $-c$ to be congruent to $2^{a}$ modulo $p$. (Key phrase: covering congruences). I could write some more, but I can't really do any better than the following very nice elementary talk by Carl Pomerance:

www.math.dartmouth.edu/~carlp/PDF/covertalkunder.pdf

Apparently the collective number theory brain of mathoverflow is remaking 150 year old conjectures that have been known to be false for over 50 years! I was going to let this post consist of the first line, but I guess I'm feeling generous today. On the other hand, I'm increasingly doubtful that I'm going to get an answer to question 2339.

Answer 2

There are certainly (many!) pairs of integers $c$, $d$ for which it's known that $2^n + c$, $2^n + d$ can't be simultaneously prime infinitely often -- take $c = 1$, $d = -1$, for instance, where $2^n - 1$ can only be prime if $n$ is prime, but $2^n + 1$ can only be prime if $n$ is a power of $2$. Alternatively, taking everything $\bmod 3$, we see that $c = -1$, $d = 7$ are only simultaneously prime at $n = 2$.

So there are lots of local obstructions to these pairs being simultaneously prime, although probably not enough to rule out all but finitely many of them.

[Edited because this is unlikely to fit in a comment]: Here's a rough stab at a really basic heuristic (for part 1 and part 3) which I don't see a way to make actually work, but maybe someone else will...

So let's fix $c$ and consider the $\bmod p$ behavior of $2^n + c$ for each odd prime $p$. Since $2^n$ is periodic $\bmod p$, for large $n$ we have some congruence classes $\bmod {(p-1)}$ for which $2^n + c$ is always composite. To simplify the analysis, we can just consider the behavior at $p$ such that $2$ is a primitive root $\bmod p$, in which case there's exactly one such congruence class $\bmod {(p-1)}$ for every $p$.

The problem now is that there's no obvious way to sieve this, since the primes minus one don't behave very nicely with respect to multiplication. My initial hunch -- which is only a hunch, not backed up by anything resembling logic -- is that generically speaking, we might see roughly the same behavior as if we were to sieve by the primes, i.e., $2^n + c$ is coprime to all the primes for which $2$ is a primitive root with probability $1/\log n$. This is much larger than the PNT predicts, of course, but notably it's still small enough that (assuming my back-of-the-envelope calculation and wildly speculative hunch are correct) we should expect that $2^n + c$, $2^n + d$ are typically simultaneously prime only finitely often.

[Edit 2]: So after some more thought I see where my hunch is horribly, horribly wrong, namely that there's no reason to believe that $a \equiv b \pmod {(p-1)}$ and $a \equiv d \pmod {(q-1)}$ has any solutions. But I do suspect that we do get some "new" forbidden exponents for almost every prime, which ::waves hands vigorously:: suggests that the values of $n$ with $2^n + c$ prime do have density $0$ and in particular probably have density at most $O(1/\log n)$, which is still good for a heuristic for (3). Can anyone make this more precise?

Answer 3

Hi there, I hope I'm not duplicating anything with what I will write. Here goes: If one considers the Bateman-Horn conjecture, it predicts that $$ \sum_{n \leq x}\Lambda(f(n)) \sim \prod_p\left(\frac{p-n_p}{p-1}\right)x $$

where $\Lambda(n)$ is the von Mangoldt function and $n_p$ is the number of solutions to the equation $f(n) \equiv 0 \bmod p$ in $\mathbb{Z}/p\mathbb{Z}$. The reason for the form of each Euler factor is as follows: For each $p$, usually there is $(p-1)/p$ chance of nondivisibility by $p$ in the integers. But if the set in consideration is the image of the polynomial $f$, then the new probability of nondivisibility by $p$ is $(p-n_p)/p$. So the Euler factor is $((p-n_p)/p)/((p-1)/p) = (p-n_p)/(p-1)$. Whether the infinite product over these factors is zero or not is like a competition between primes with $n_p=0$ and $n_p>1$. It really depends on the density of these primes with various $n_p$.

Therefore I'd be curious to know whether the above Bateman-Horn conjecture can be generalized to this case as follows(?): $$ \sum_{n \leq x}\Lambda(2^n+c) \sim \prod_p\left(\mbox{something}\right)x. $$

Or is there any reason why heuristics for $2^n+c$ must be treated differently from $f \in \mathbb{Z}[x]$?

It is interesting to consider something analogous to $n_p$ in the case of $2^n+c \equiv 0 \bmod p$. For $p|c$, we have $n_p=0$ since $2^n$ will never be $0 \bmod p$. For $p\nmid c$, one must consider the cyclic subgroup $<2>$ generated by $2$ in $(\mathbb{Z}/p\mathbb{Z})^{*}$. Let $h$ be the order of this subgroup. We have $h | p-1$. Let $\delta_p = 1$ if $c \in <2>$ and $\delta_p=0$ otherwise.

Then for each $p$, numbers of the form $2^n+c$ have probability $$(\delta_p \times (p-1)/h)/(p-1) = \delta_p / h$$ of divisibility by $p$. Therefore, perhas the Euler factor here should be (?) $$ \left(\frac{(h-\delta_p)/h}{(p-1)/p}\right). $$

Putting all this together, can one conjecture (?) $$ \sum_{n \leq x}\Lambda(2^n+c) \sim \prod_{p|c}\left(\frac{p}{p-1}\right)\prod_{p \nmid c}\left(\frac{(h-\delta_p)/h}{(p-1)/p}\right)x. $$

Thanks.

Answer 4

Naive conjecture for (2) and (3) would be that there are only finitely many such $n$ (unless $c=d$, since then (3) becomes (1)). The reason is that heuristically the 'probability' that a number of order $m$ is prime is roughly $1/\log(m)$, and the sum $$\sum_n \frac{1}{\log(2^n+c)\log(2^n+d)}$$ converges.

Answer 5

A heuristic approach might be to examine how many large primes are known for a given $c$.

A good source is Probable Primes Top 10000

The search form is here

Some results from the PRP Top 10000 dabase:

c largest-n number-of-primes-in-the-database:
3 479844 11
5 193965 4
7 566496 6
9 173727 6
11 345547 6
13 175628 2

Probably the computational effort for different $c$ in the database is quite different.

OEIS has data too.

Answer 6

Hi, I believed that there are always an infinitude of primes in all forms of 2^n + c except c = 1 (fermat numbers). I don't have a proof though but gathering some data on my research of forms 2^x+3 and 2^x+5. I am interested the reason being that together they will produce infinite twin primes and prime arithmetic progression for (3,2^x+3,2^x+1 + 3), again just my belief and based on algorithm I am working on.