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?



Is there a 2-power-twinless prime?
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.


