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](https://doi.org/10.1090/mcom/3537) 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$)?



Hamming distance to primes
See OEIS sequences [A067760](https://oeis.org/A067760) and [A076336](https://oeis.org/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.


