Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime?

Solution 1:

The congruential argument below shows that we need only worry about the safe prime $7$.

An odd power of $2$ is congruent to $-1$ modulo $3$. Let $p$ be a safe prime. Then, except in the cases $p=5$ and $p=7$, $p$ is of the form $2(6k\pm 1)+1$. But $p$ cannot be of the form $2(6k+1)+1$, so it is of the form $2(6k-1)+1$, that is, $p$ is congruent to $-1$ modulo $3$. The safe prime $5$ is also congruent to $-1$ modulo $3$. (The only safe prime that escapes this congruential net is $7$.)

So if $2^{2n+1}=p+q$, where $p$ is a safe prime other than $7$, then $q$ must be divisible by $3$. In particular, if $q$ is prime, $q$ must be $3$.

But this is not possible, since (apart from the case $p=5$) a safe prime $p$ is congruent to $3$ modulo $4$, and hence $p+3$ is congruent to $2$ modulo $4$. The case $p=5$ accounts for the decomposition $8=5+3$.

Thus if $2^{2n+1}=p+q$, where $p$ and $q$ are primes and $p$ is safe, we must have $p=7$. So the only question that remains is to look for primes $q$ of the form $q=2^{2n+1}-7$.

There likely is some literature on primes of the form $2^{2n+1}-7$. A feeble attempt at experimentation did not locate any, but there is certainly not always a simple small divisor.

Solution 2:

From Nicolas's argument I realized that it was sufficient to check if $2^{2n+1}-7$ was prime. A much easier task than the usual brute forcing. After a few minutes of manual testing on wolfram alpha I found that $2^{39}$ could indeed be written as the sum of a prime and a safeprime:

$$7+549755813881=549755813888=2^{39}.$$

Edit: I wrote a sage program to check all of the odd powers of two less than 2000. It seems I was a bit lucky since the next examples are 715 and 1983. I checked OEIS and numbers such that $2^{n}-7$ are prime has its own page.