For any positive integer $k$, are there always primes $p$ and $q$ such that $q-p=2^k$?

Question

Experimental evidence suggests to me that there are always primes $p$ and $q$ such that $q-p=2^k$.

Some examples include: $5-3=2$, $11-7=4$, $19-11=8$, $29-13=16$, $43-11=32$, etc.

I am now sure how to go about proving this. It seems like it should be accessible enough, perhaps using something like Dirichlet's theorem for primes ($a+bk$ is prime for infinitely many $k$ if $\gcd(a,b)=1$).

Can someone help me prove or disprove this?

Answer 1

Not an answer, but a few data points. The table shows the smallest solution for each power of $2$. As we can see, the smallest $q$ is usually pretty close to the power of $2$, that is, $p$ is quite small, but unfortunately not small enough to be predictable.

\begin{array}{rrrr} k & 2^k & q & p \\ 0 & 1 & 3 & 2 \\ 1 & 2 & 5 & 3 \\ 2 & 4 & 7 & 3 \\ 3 & 8 & 11 & 3 \\ 4 & 16 & 19 & 3 \\ 5 & 32 & 37 & 5 \\ 6 & 64 & 67 & 3 \\ 7 & 128 & 131 & 3 \\ 8 & 256 & 263 & 7 \\ 9 & 512 & 523 & 11 \\ 10 & 1024 & 1031 & 7 \\ 11 & 2048 & 2053 & 5 \\ 12 & 4096 & 4099 & 3 \\ 13 & 8192 & 8209 & 17 \\ 14 & 16384 & 16421 & 37 \\ 15 & 32768 & 32771 & 3 \\ 16 & 65536 & 65539 & 3 \\ 17 & 131072 & 131101 & 29 \\ 18 & 262144 & 262147 & 3 \\ 19 & 524288 & 524341 & 53 \\ 20 & 1048576 & 1048583 & 7 \\ 21 & 2097152 & 2097169 & 17 \\ 22 & 4194304 & 4194371 & 67 \\ 23 & 8388608 & 8388619 & 11 \\ \end{array}

Answer 2

Claim: Yes, there are always primes $(p,q)$ such that their difference is $2^k$ for all positive integers k.

Idea: Assume the contrary for some $k$. Then, for all primes p, $2^k+p$ is composite. By Green-Tao Theorem, primes contain arbitrarily large arithmetic progressions. Hence, for any positive integer $n$ there exists primes $p_1,p_2,...,p_n$ such that they form an arithmetic progression. Then, $2^k+p_1,2^k+p_2,...,2^k+p_n$ also forms an arithmetic progression. Since we can get n sufficiently large, we can see by Dirichlet's theorem that there must exist one prime $p$ such that $2^k+p$ is prime. Hence, we have a solution, $(2^k+p,p)$. Contradiction.

Hence, for all positive integers $k$, there exists pirmes $(p,q)$ such that $p-q = 2^k$

Note that this is not a proof but suggest only why it might exist.