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?

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

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.