6
$\begingroup$

Call two primes 2-power-twins if their difference is (can you guess?) a power of 2. For example, 11 and 19 are 2-power-twins.

Is there a 2-power-twinless prime?

I would imagine that this is doable the following way.

If I take a prime of the form $3k+1$, then I know that adding an odd power of 2 or subtracting an even power of 2 cannot give a prime.

If I take a prime of the form $5k+1$, then I know that adding a power of 2 that is $2\bmod 4$ cannot give a prime.

Do such observations give enough conditions to conclude the existence of a 2-power-twinless prime from Dirichlet's theorem?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ You should exclude the obvious fact that $2$ is a $2$-power-twinless prime. $\endgroup$
    – Tony Huynh
    Commented Dec 4, 2018 at 10:21
  • 2
    $\begingroup$ Brun sieve gives a bound for $\sum_{n \le x} 1_{n \in P, n-2^k \in P}$ $\endgroup$
    – reuns
    Commented Dec 4, 2018 at 10:28
  • 2
    $\begingroup$ $ 2 + 2^0 = 3 $ $\endgroup$
    – Tom
    Commented Dec 4, 2018 at 12:49
  • 1
    $\begingroup$ @Tony See Tom's comment. $\endgroup$
    – domotorp
    Commented Dec 4, 2018 at 12:51
  • $\begingroup$ @reuns I don't see why that's useful. $\endgroup$
    – domotorp
    Commented Dec 4, 2018 at 12:51

1 Answer 1

Reset to default
9
$\begingroup$

Erdos proved that there is an arithmetic progression of odd numbers, none of which can be expressed as a sum of a power of two and a prime. I believe one can arrange for such an arithmetic progression to satisfy the hypotheses of Dirichlet's Theorem on primes in arithmetic progression, so that means there are infinitely many primes $p$ for which there is no prime $q$ such that $p-q$ is a power of two. So there are infinitely many primes $p$ that are not the larger of a pair of two-power-twins.

The Erdos result, from the 1950 paper in which he introduced covering congruences, has been expanded upon. I think it has been proved that there is an arithmetic progression of odd numbers $n$ such that $n$ is neither of the form $2^k+q$ nor of the form $q-2^k$ for any prime $q$ (but I don't have easy access to a citation for this). Modulo satisfying the Dirichlet hypothesis, this would establish the existence of infinitely many 2-power-twinless primes.

I think the appropriate citation is F. Cohen, J.L. Selfridge, Not every number is the sum or difference of two prime powers, Math. Comp. 29 (1975) 79–81. Theorem 1 states, there exists an arithmetic progression of odd numbers which are neither the sum nor difference of a power of two and a prime. They give the example, 47867742232066880047611079 is prime and neither the sum nor difference of a power of two and a prime.

Improve this answer
$\endgroup$
3

You must log in to answer this question.

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