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 [1]. 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?
[1] Note that the bit flipped may be higher than the most significant bit of the number, unless ruled out as in the paragraph above. Several people have asked “What about 85?” It is true that flipping any of the seven lowest bits of 85 will not yield a prime. But flipping a zero bit in a more significant position will give a prime. For example, 1024 + 85 is prime. Bur for 2131099 it is not possible to add any larger power of 2 to the number and produce a prime.
Oof. Is there some intuition from the prime number theorem? I.e., among the first N integers, the number of primes is about N/log(N). The number of bits in N is O(log(N)), so it wouldn’t be surprising for a large proportion of odd numbers to be a bit-flip away from a prime.
However, the question as stated allows any arbitary leading 0 bit to be flipped, which is quite a lot more general… hmm.
Unless I misread the OES entry or am confused, it looks like 78557 = 17*4621 is neither prime nor a bit flip away from a prime and 78557 < 2131099.
78557 = 0b10011001011011101
78553 = 0b10011001011011001, flipping third bit from right
78553 is prime
My bad… addition is not bit flipping unless there is no carry.
If you allow flipping bits larger than the number you started with, it would be surprising if there were any odd number that could not be bit flipped into a prime. (Any number could be bit flipped into infinitely many numbers, and the probabilities of those being prime are asymptotically the harmonic series, so the expected number of primes that can be obtained by bit flipping is infinity.)
If you don’t, I would expect similar results to the previous post about adding powers of 2; although the mechanism is different, the number of candidates and their magnitudes are roughly the same, so I would expect a fixed proportion of odd numbers to become primes with 1 bit flip, and all or all but finitely many odd numbers to become primes with 2 bit flips (for reasons I explained in a comment on that post).
I was curious about this as well – but all the evidence which points to 2131099 not being a bit flip away from a prime, also points to 2510177 having the same property (it’s another Sierpinski number, and flipping any of its 1s to 0s gives a composite number). Unlike 2131099, 2510177 is not prime.