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

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.

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?

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.