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

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

2009-11-13T07:46:39Z

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 by Boris Bukh for Infinitely many primes of the form 2^n+c as n varies?

2009-11-13T09:08:06Z

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 by Harrison Brown for Infinitely many primes of the form 2^n+c as n varies?

2009-11-13T12:15:50Z

There are certainly (many!) pairs of integers c, d for which it's known that 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 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?

Answer by Jaime Montuerto for Infinitely many primes of the form 2^n+c as n varies?

2009-11-13T14:03:13Z

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.

Answer by Lavender Honey for Infinitely many primes of the form 2^n+c as n varies?

2009-11-13T15:11:59Z

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.

Answer by Timothy Foo for Infinitely many primes of the form 2^n+c as n varies?

2011-10-20T05:22:35Z

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 by joro for Infinitely many primes of the form 2^n+c as n varies?

2011-10-20T07:20:37Z

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.