Prime Numbers in Binary

Prime Numbers in Binary

We usually see numbers represented in base 10 "decimal" notation, and almost all prime number lists use base 10. But we can represent numbers in any base we please. In base 10 we use 10 symbols 0,1,2,3,...,9 and in base n we use n symbols 0,1,2,3,...,(n-1)

The simplest base is 2, because in that base we have only 2 symbols 0,1

Base 2 is also call "binary" and writing numbers in binary makes them look like computer data.

In binary the positions represent 1,2,4,8,16,32,.. so the general representation of a positive integer n is..

n=sum{ai*2^i} where the coefficients {ai} are all 0 or 1 and the sum is over i from 0 to some upper limit.

Notice that, despite the left to right standard mathematical summation above, many people use the right to left notation when writing binary numbers. I don't like it, but I'll use it anyway!

So here's the first 50 prime numbers in binary..

2 10
3 11
5 101
7 111
11 1011
13 1101
17 10001
19 10011
23 10111
29 11101
31 11111
37 100101
41 101001
43 101011
47 101111
53 110101
59 111011
61 111101
67 1000011
71 1000111
73 1001001
79 1001111
83 1010011
89 1011001
97 1100001
101 1100101
103 1100111
107 1101011
109 1101101
113 1110001
127 1111111
131 10000011
137 10001001
139 10001011
149 10010101
151 10010111
157 10011101
163 10100011
167 10100111
173 10101101
179 10110011
181 10110101
191 10111111
193 11000001
197 11000101
199 11000111
211 11010011
223 11011111
227 11100011
229 11100101

Writing numbers in binary can help spot patterns we might not notice in other bases. For example..

In binary all prime numbers except 2 begin and end with 1.

The first 2 digits of the prime 71 is the prime 3 and the last 5 digits is the prime 17. So we could define a "+" operation and say that 3+17=71. Notice that the + operation depends on order, so 17+3=113 is different, but it's still a prime!

The prime 13 is just the prime 11 written backwards. The same is true for 23 and 29 and lots more. Many primes are just an earlier prime written backwards!

Some primes have all digits set to 1, so these primes are of the form (2^n)-1 where n is just the number of binary digits. Primes of this form are called Mersenne primes, named after Marin Mersenne, a French monk who studied them in the 17th century.

Here's another interesting thing. The twin prime pair (1049,1051)=(10000011001,10000011011) in binary. Now concatenate the binary bit streams to get 1000001100110000011011=2149403 and this is also a prime! Primes generating primes. Quite amazing.

I wonder what we would discover if we used sophisticated computer pattern recognition on prime numbers in binary format?

Content written and posted by Ken Abbott abbottsystems@gmail.com