# Is there a 2-power-twinless prime?

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?

• You should exclude the obvious fact that $2$ is a $2$-power-twinless prime. – Tony Huynh Dec 4 at 10:21
• 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^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

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.