Search This Blog

Prime Numbers in Base 2

Prime Numbers in Base 2

We're used to seeing 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 onward.

For example, the number 11 in binary is 1101, and this simply means..


Here's the first 20 prime numbers in binary..

2 01
3 11
5 101
7 111
11 1101
13 1011
17 10001
19 11001
23 11101
29 10111
31 11111
37 101001
41 100101
43 110101
47 111101
53 101011
59 110111
61 101111
67 1100001
71 1110001

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.

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

Content written and posted by Ken Abbott

Like this post? Please share it by clicking one of the share buttons below!