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

Improve this question
$\endgroup$
4
  • $\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
    Commented 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$
    – Robert Israel
    Commented 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
    Commented 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
    Commented Aug 1, 2021 at 6:17

1 Answer 1

Reset to default
24
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .