There is a positive density of odd numbers which are of the form $2^n+p$ (due to Romanoff), and a positive density which are not of this form (due to van der Corput and Erdos, see this paper for a review and some results on the density). So, for some but not almost all odd numbers, we can get to a prime by subtracting a power of two.

I'm curious about a related question: given an odd integer $m$, is there always a prime number with Hamming distance 1 to $m$? For example, $127 = 1111111_2$ is not of the form $2^n+p$, but it has Hamming distance 1 to a prime, since $383 = 101111111_2$ is prime.

A related question, which implies the first: given an odd integer $m$, does the set $\{m+2^n\mid n\in \mathbb{N}\}$ contain infinitely many primes (or at least one for which $2^n>m$, so that this corresponds to flipping a bit in $m$)?

  • $\begingroup$ The sum from $n$ to infinity of the one over the log of $2^n+m$ is infinite, but I can't imagine trying to prove the existence of such primes with current technology. Even getting density 1 seems impossible to me - you would need to look to $n$ exponentially large in $m$. $\endgroup$
    – Will Sawin
    Jun 14, 2020 at 23:49
  • 1
    $\begingroup$ The sequence "least prime with Hamming distance 1 from the k'th odd integer" starts $3, 2, 7, 3, 11, 3, 5, 7, 19, 3, 5, 7, 17, \ldots$. It doesn't seem to be in the OEIS yet, but should be. Are you interested in contributing it? If you don't wish to, I can (with a link to this question). $\endgroup$ Jun 15, 2020 at 1:55
  • 1
    $\begingroup$ Thanks very much for your answer, I wasn't aware of the (dual) Sierpiński numbers. I'll go ahead and add this to the OEIS. $\endgroup$
    – srossd
    Jun 15, 2020 at 22:43
  • $\begingroup$ I think this question has already been asked in a slightly different form and answered here: mathoverflow.net/questions/316867/… $\endgroup$
    – domotorp
    Aug 1, 2021 at 6:17

1 Answer 1


See OEIS sequences A067760 and A076336. If $n$ is a dual Sierpiński number, there is no $k$ such that $n+2^k$ is prime. There is no prime with Hamming distance $1$ to the Sierpiński number $2131099$, and this may be the least positive integer with this property.


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.