Primes with two non-zero bits

Suppose a number n written in binary has two 1s and all the rest of its bits are zeros. If n is prime, then the 1s must be the first and last bits of n. The first bit is 1 because the first bit of every positive integer is 1. The last bit is 1 because if the second 1 appeared anywhere else then n would be divisible by 2.

Here are the first four examples:

11_two = 3_ten
101_two = 5_ten
10001_two = 17_ten
100000001_two = 257_ten

Let's count how many 0 bits each number contains. We get 0, 1, 3, and 7 if we count in base 10, or 0, 1, 11, and 111 if we count in binary. It seems that the number of 0 bits is either zero or a number whose binary representation is all 1s. In fact this turns out to be a theorem:

Suppose a number n is written in binary as a 1, followed by m 0's, and finally a 1. Then if n is prime, then either m = 0 or the binary representation of m consists entirely of 1's.

To prove this theorem, let's move away from talking about bits and move toward more standard math terminology.

Our description of n in terms of bits is another way of saying

n = 2^k + 1.

And our description of m is another way of saying

m = 2^j - 1.

And a 1 followed by m 0's and then a 1 is a number of the form

2^m+1 + 1.

So the theorem above is saying that if 2^k + 1 is a prime number, then k is a power of 2.

Here's a proof. Suppose k is not a power of 2. Then k has an odd factor, i.e. k = ab where b > 1 is an odd number. In that case we can factor 2^k + 1 as follows:

We've shown above that 2^k + 1 is prime when k = 2^j and j = 0, 1, 2, and 3.

What about j = 4? Yes, 2¹⁶ + 1 = 65537 is prime.

We're on a roll. What about j = 5? Is 2³² + 1 prime? No, it's not.

What about larger values of j? Do any of them produce primes? Nobody knows.

This post has secretly been about Fermat primes. The nth Fermat number is given by

Fermat observed that F_n was prime for n = 0, 1, 2, 3, and 4. He conjectured that F_n is prime for all n, but Euler factored F₅, disproving Fermat's conjecture.

Why did this post delay using standard terminology? The first reason was to unpack the math. The direct discussion can go by so quickly that it's hard to appreciate what it is going on. The second reason was to illustrate how much easier things can become when we switch from discussing bit patterns to using math notation. Sometimes things go the other way, with bits being easier to understand than mathematical equations.

The post Primes with two non-zero bits first appeared on John D. Cook.