Infinitely many primes of the form 2^n+c as n varies? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:46:06Z http://mathoverflow.net/feeds/question/5323 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies Infinitely many primes of the form 2^n+c as n varies? Kevin Buzzard 2009-11-13T07:46:39Z 2011-10-20T07:20:37Z <p>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.</p> <p>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!]</p> <p>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.</p> <p>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?]</p> <p>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$".</p> <p>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".</p> http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies/5328#5328 Answer by Boris Bukh for Infinitely many primes of the form 2^n+c as n varies? Boris Bukh 2009-11-13T09:08:06Z 2009-11-13T09:13:39Z <p>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.</p> http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies/5338#5338 Answer by Harrison Brown for Infinitely many primes of the form 2^n+c as n varies? Harrison Brown 2009-11-13T12:15:50Z 2009-11-13T14:39:05Z <p>There are certainly (many!) pairs of integers c, d for which it's <em>known</em> that <img src="http://latex.mathoverflow.net/png?2%5En%20%2B%20c%2C%202%5En%20%2B%20d" alt="2^n + c, 2^n + d" title="" /> 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.</p> <p>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.</p> <p>[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...</p> <p>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.</p> <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 <em>generically</em> 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 <img src="http://latex.mathoverflow.net/png?2%5En%20%2B%20c%2C%202%5En%20%2B%20d" alt="2^n + c, 2^n + d" title="" /> are typically simultaneously prime only finitely often.</p> <p>[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 <em>some</em> "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?</p> http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies/5348#5348 Answer by Jaime Montuerto for Infinitely many primes of the form 2^n+c as n varies? Jaime Montuerto 2009-11-13T14:03:13Z 2009-11-13T14:03:13Z <p>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.</p> http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies/5367#5367 Answer by Lavender Honey for Infinitely many primes of the form 2^n+c as n varies? Lavender Honey 2009-11-13T15:11:59Z 2009-11-13T18:14:05Z <p>Buzzard is correct to be skeptical of the most naive arguments: Erdos observed that $2^n + 9262111$ is never prime.</p> <p>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:</p> <p>www.math.dartmouth.edu/~carlp/PDF/covertalkunder.pdf </p> <p>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 <a href="http://mathoverflow.net/questions/2339/" rel="nofollow">question 2339</a>. </p> http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies/78644#78644 Answer by Timothy Foo for Infinitely many primes of the form 2^n+c as n varies? Timothy Foo 2011-10-20T05:22:35Z 2011-10-20T05:22:35Z <p>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$$</p> <p>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$.</p> <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.$$</p> <p>Or is there any reason why heuristics for $2^n+c$ must be treated differently from $f \in \mathbb{Z}[x]$?</p> <p>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 $&lt;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 &lt;2>$ and $\delta_p=0$ otherwise. </p> <p>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).$$ </p> <p>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.$$</p> <p>Thanks.</p> http://mathoverflow.net/questions/5323/infinitely-many-primes-of-the-form-2nc-as-n-varies/78649#78649 Answer by joro for Infinitely many primes of the form 2^n+c as n varies? joro 2011-10-20T07:20:37Z 2011-10-20T07:20:37Z <p>A heuristic approach might be to examine how many large primes are known for a given $c$.</p> <p>A good source is <a href="http://www.primenumbers.net/prptop/prptop.php" rel="nofollow">Probable Primes Top 10000</a></p> <p>The search form is <a href="http://www.primenumbers.net/prptop/searchform.php" rel="nofollow">here</a></p> <p>Some results from the PRP Top 10000 dabase:</p> <pre><code>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 </code></pre> <p>Probably the computational effort for different $c$ in the database is quite different.</p> <p>OEIS has <a href="https://oeis.org/A057732" rel="nofollow">data</a> too.</p>