-2
$\begingroup$

This is a question about generalizations of the twin primes conjecture.

I would like to know a counterexample, or a proof, for the following couple of related arithmetical sentences. The first is

$(\forall p) Prime(p) \Rightarrow (\exists n)(\exists q)(Prime (q) \wedge (p = 2^n + q))$

More informally, if $p$ is prime, then $p$ can be written as the sum of a smaller prime $q$ and a power of $2$. The second is

$(\forall q) Prime(q) \Rightarrow (\exists n)(\exists p) (Prime(p) \wedge (p = 2^n + q))$

More informally, if $q$ is prime, then there exists a number $n$ such that the sum of $q$ and the $n$-th power of $2$ is a prime number.

Improve this question
$\endgroup$
8
  • $\begingroup$ Is $n$ allowed to be $0$? $\endgroup$
    – JRN
    Commented Oct 23, 2016 at 23:57
  • $\begingroup$ For the first statement, what if $p=2$? $\endgroup$
    – JRN
    Commented Oct 23, 2016 at 23:59
  • 1
    $\begingroup$ And $p=127$ is the first counterexample to the statement you intended. $\endgroup$
    – Steven Landsburg
    Commented Oct 24, 2016 at 0:00
  • 1
    $\begingroup$ For OP: Check out this paper of Erdos renyi.hu/~p_erdos/1950-07.pdf -- it answers at least the first of your questions, and the second should be similar. $\endgroup$
    – Lucia
    Commented Oct 24, 2016 at 0:07
  • 1
    $\begingroup$ @Lucia, I'm with Steven here. If one can't write properly in formal language, one should not use it, specially if plain english can make the statement perfectly precise. $\endgroup$
    – Ramiro de la Vega
    Commented Oct 24, 2016 at 0:09

1 Answer 1

Reset to default
7
$\begingroup$

This was solved by Erdos, who introduced the idea of a covering congruence. Erdos shows that if $n$ is congruent to $1\pmod 2$, $1\pmod 7$, $2\pmod 5$, $8\pmod {17}$, $2^7 \pmod{13}$, $2^{23} \pmod {241}$, then $n$ is not the sum of a prime and a power of $2$. Now this progression is of the form $a\pmod{2\times 5\times 7\times 13\times 17\times 241}$ with $a$ coprime to the modulus, and therefore by Dirichlet contains infinitely many primes. This shows that there are infinitely many counterexamples to the first statement. See also Cohen and Selfridge which should answer your other question too.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .