Someone asked an interesting question on MathOverflow: given an odd number, can you always flip a bit in its binary representation to make it prime? It turns out the answer is no, but apparently it is very often the case an odd number is just a bit flip away from being prime.
I find that surprising.
Someone pointed out that 2131099 is not a bit flip away from a prime, and that this may be the smallest example.
The counterexample 2131099 is itself prime, so you could ask whether an odd number is either a prime or a bit flip away from a prime.
Is this always the case? If not, is it often the case? The MathOverflow question was stated in terms of Hamming distance, counting the number of bits in which two bit sequences differ.
It asked whether odd numbers are always Hamming distance 1 away from a prime.
My restatement of the question asks whether the Hamming distance is always at most 1, or how often it is no more than 1.
You could ask more generally about the Hamming distance to the nearest prime.
Is it bounded, if not by 1, then by another finite number? If so, what is the smallest such bound? What is the probability that its value is 1? Etc.
This ties into a couple of other things I’ve blogged about.
A few weeks ago I wrote about new work on the problem of finding the proportion of odd numbers that can be written as the sum of a power of 2 and a prime.
That’s a little different problem since bit flipping is taking the XOR (exclusive or) and not always the same as addition.
It also leaves out the possibility of flipping a bit beyond the most significant bit of the number, i.
e.
adding to a number n a power of 2 greater than n.
Another related post is on the Rowhammer attack on public key cryptography.
By flipping a bit in the product of two primes, you can produce a number which is much easier to factor.
These two posts suggest a variation on the original problem where we disallow flipping bits higher than the most significant bit of n.
So giving a k-bit number n, how often can we flip one of its k bits and produce a prime?.