12
$\begingroup$

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

$\endgroup$
  • $\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 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$ – Robert Israel Jun 15 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 at 22:43
21
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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