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

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was surprised to discover that $32$, $128$, $512$, and $2048$ cannot be represented in this way, and I've since found that the same is true for $8192$, $32768$, $131072$, $524288$, $2097152$, and $8388608$. Is there any counterexample? If not, how can it be proved?

-

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.

-
Wow! ........... (39 of these) – Dan Brumleve Sep 14 '11 at 6:50

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.

-
I have: $2^{2k+1} = q + r$, $r = 2p+1$, $4^k = p + (q+1)/2$. What am I missing? – Dan Brumleve Sep 14 '11 at 6:12
Ahh, got it. Now I wonder if there are any other classes of exceptions that invalidate the heuristic argument I suggested in my answer to the other question? – Dan Brumleve Sep 14 '11 at 6:16
But I guess it is still possible that $2^{2k+1} = 7+q$ for some prime $q$? This is a great answer but I've unaccepted it for the moment. – Dan Brumleve Sep 14 '11 at 6:38
@Dan Brumleve: No problem, easy come easy go. It is not often that simple congruential conditions get us this far. Yes, $7$ is the only possible exception. The weird safe primes are $5$ and $7$, and $5$ was no trouble. – André Nicolas Sep 14 '11 at 6:51
@Dan Brumleve: A little mulling over numbers showed that the difference between $2^{2n+1}$ and a safe prime is usually divisible by $3$. Paid no attention to $7$ since it is obviously special. So had to rule out a difference of $3$ (easy) and $7$ (not easy, indeed as it turns out not possible). – André Nicolas Sep 14 '11 at 7:06