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

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

-
Fermat primes have the form $2^{2^n}+1$. –  Kevin O'Bryant Oct 21 '11 at 1:21
Yes but it's an easy exercise to check that if $2^n+1$ is prime then it's a Fermat prime. –  Kevin Buzzard Oct 22 '11 at 8:37

Buzzard is correct to be skeptical of the most naive arguments: Erdos observed that $2^n + 9262111$ is never 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.

-
I didn't make a conjecture---I asked a question ;-) Fabulous post FC; thanks. –  Kevin Buzzard Nov 13 '09 at 15:38
Actually, looking at 2339 I see you've accused me of making a conjecture there too, whereas if I look at the source I again see that I only asked a question :-) –  Kevin Buzzard Nov 13 '09 at 15:41
@buzzard: it happens to the best of us, even Serre and Poincare. –  Harrison Brown Nov 13 '09 at 15:42
@FC: aah, thanks. I deleted the comment containing the misunderstanding, thus throwing the comments into some sort of minor chaos. –  Kevin Buzzard Nov 13 '09 at 16:36
Finally I'll remark that it was Swinnerton-Dyer that has caused all this trouble. I had a couple of pints of cider with him once and then he let fly about conjectures these days not being worth anything, and how he remembered the good old days (by which I think he meant the sixties) when conjectures were things that were most certainly true, and everything else was just a question. Since that conversation I've been much more reluctant to conjecture anything! –  Kevin Buzzard Nov 13 '09 at 16:38

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 (mod 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 (mod p) behavior of 2^n + c for each odd prime p. Since 2^n is periodic (mod p), for large n we have some congruence classes (mod 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 (mod p), in which case there's exactly one such congruence class (mod 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 = b (mod p-1) and a = d (mod 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?

-
Yes. Indeed Anton's comment in 5191 gives another example (c=3,d=5) where there's a (similar-looking but slightly harder) proof that they can both only be prime finitely often. I also agree that probably the local conditions won't always save you (again follow Anton's idea and find explicit n,c,d such that 2^n+c and 2^n+d aren't prime but only have nice juicy prime factors of size > 10^6). So now we need some sensible heuristics to continue, if there are any sensible heuristics on these matters. I guess it's also worth remarking that no-one has said anything about Q1 yet. –  Kevin Buzzard Nov 13 '09 at 12:25

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.

-
That seems unreasonable: the Euler product form in the twin prime, Schinzel, Bateman-Horn, etc, conjectures have their source in the Chinese Remainder Theorem (independence of reductions of integers modulo distinct primes). The analogue property fails for powers of $2$. (Or of any other integer $a\geq 2$). This is also why, for instance, sieve methods are unsuccessful for these types of questions. –  Denis Chaperon de Lauzières Oct 20 '11 at 7:11
Ah, thanks very much. I really should have read the Lenstra-Pomerance-Wagstaff conjectures (en.wikipedia.org/wiki/Mersenne_conjectures) before I said the above. Thanks. –  Timothy Foo Oct 20 '11 at 9:39

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.

-
In general I am nervous about these sorts of heuristics, because applied naively they would predict infinitely many Fermat primes, whereas applied more sensibly (i.e. think about which n can occur from an elementary viewpoint first and then heuristicise) they predict finitely many. On the other hand I don't think this specific objection (my nervousness about heuristics) applies to your heuristics (because if we made intelligent elementary observations which ruled out certain n first then the sum would only get smaller). So I think you've probably done (2) and (3). –  Kevin Buzzard Nov 13 '09 at 9:19
Actually, suddenly I am nervous about this argument. If c=1 then one can say a lot about possible factors of 2^n+c, for example, and a competing heuristic on the Wikipedia page for Fermat primes seems to say that incorporating these facts screws up the heuristic that there are only finitely many Fermat primes. Does a general heuristic look like this: "here are some things I can think of, now let's assume everything else is random and sum 1/log"? So implicit in such a heuristic is the assertion that you've not missed anything? –  Kevin Buzzard Nov 13 '09 at 10:13
Ok here is an explicit comment about your heuristic that I hope worries you. If 2 is not a primitive root mod a prime number q, then q might never divide 2^n+c (e.g. 7 never divides 2^n+9 and surely there will be other primes, possibly infinitely many more, with this property---certainly 2 never divides 2^n+9 either). Hence 2^n+9 is less likely to be composite than a random large number. For a proper heuristic you need to take this into account and recalculate. What I'm saying is that your heuristic might be too naive, and fixing it up to incorporate my comments might give a different answer –  Kevin Buzzard Nov 13 '09 at 10:17
I share your anxiety about these heuristics in general, and extreme naivete of mine in particular. For example, by these heuristics would give that if alpha is a real number, then floor(alpha^(3^n)) is prime finitely often. However, it is false for some alpha. –  Boris Bukh Nov 13 '09 at 10:43

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.

-
In the other thread there is already a proof that 2^x+3 and 2^x+5 will not produce infinitely many twin primes, and there is also a bunch of evidence to suggest that 3,2^x+3,2^{x+1}+3 will not produce infinitely many sets of three primes in an AP. –  Kevin Buzzard Nov 13 '09 at 14:21
Thanks for this, now I concede about this result, of course my original question still holds. How big x exponent is? I would imagine it to be big. –  Jaime Montuerto Nov 13 '09 at 18:41

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.

-