6
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ You should exclude the obvious fact that $2$ is a $2$-power-twinless prime. $\endgroup$
    – Tony Huynh
    Dec 4, 2018 at 10:21
  • 2
    $\begingroup$ Brun sieve gives a bound for $\sum_{n \le x} 1_{n \in P, n-2^k \in P}$ $\endgroup$
    – reuns
    Dec 4, 2018 at 10:28
  • 2
    $\begingroup$ $ 2 + 2^0 = 3 $ $\endgroup$
    – Tom
    Dec 4, 2018 at 12:49
  • 1
    $\begingroup$ @Tony See Tom's comment. $\endgroup$
    – domotorp
    Dec 4, 2018 at 12:51
  • $\begingroup$ @reuns I don't see why that's useful. $\endgroup$
    – domotorp
    Dec 4, 2018 at 12:51

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.