# Hamming distance to primes

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$$)?

• 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$. Jun 14 '20 at 23:49
• 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). Jun 15 '20 at 1:55
• 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. Jun 15 '20 at 22:43
• I think this question has already been asked in a slightly different form and answered here: mathoverflow.net/questions/316867/… Aug 1 at 6:17

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.