Base 2 Primes

In the base 10 number system, All prime numbers greater than 10 end in 1,3,7, or 9. What if we looked at primes in base 2, does that reveal patterns of its own?

In Go, the math/big package provides a ProbablyPrime method which accurately reports primes up to $2^{64}$

import (
    "math/big"
    "fmt"
)
func printPrimesTo(n int64) {
	var i int64
	for i <= n {
		isPrime := big.NewInt(i).ProbablyPrime(1)
		if isPrime {
			fmt.Printf("%d: %b\n", i, i)
		}
		i++
	}
}

The prime numbers up to 100 represented in base 2:

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

All of the primes have their least significant bit set. Numbers without the least bit set are always divisible by two. Not all numbers that have the least bit set are prime. Nine (1001 in base 2) is not prime.

Occasionally, a prime number in base 2 consists of all ones.

1:   1
3:   11
7:   111
31:  1111
127: 1111111

In base 2, any number equal to $2^{n}-1$ will be a number of all ones. When $2^{n}-1$ is prime for some n, it’s called a Mersenne prime. Computers work primarily well in base 2 and makes searching these types of primes faster than others. As a result, the largest known primes are Mersenne primes.

// Test the primality of 2^n-1 using the Lucas-Lehmer primalty test
func LucasLehmer(n int64) bool {
	var s int64 = 4
	var m = int64(math.Pow(2, float64(n))) - 1

	for i := int64(0); i < n-2; i++ {
		s = ((s * s) - 2) % m
	}
	if s == 0 {
		return true
	}
	return false
}

The Great Internet Mersenne Prime Search (GIMPS) made use of the Lucas-Lehmer primality test from 1996-2018. 52 Mersenne primes are known. The largest, discovered in 2024, contains 41 million digits.

For comparison. A 64 bit integer can hold a max number of $2^{64}-1$ (18,446,744,073,709,551,615). A very large number, but only 20 digits long.