Playing with Mersenne Numbers

The largest prime number we’re currently aware of has 22,338,618 digits. It was discovered in January 2016 thanks to the coordinated effort of thousands of machines across the globe.

It is:

[tex]\displaystyle 2^{74,207,281}-1[/tex]

As many readers will know, this is a Mersenne prime number. The overwhelming majority of the largest prime numbers we’ve discovered over the past century have been Mersenne numbers.

A brief introduction to Mersenne Numbers

Mersenne numbers are defined as:

[tex]\displaystyle M_n \equiv 2^n-1[/tex]

for n in [tex]\mathbb{N}[/tex].

Not all Mersenne numbers are prime (e.g., [tex]M_4 = 15[/tex]), and not all prime numbers are Mersenne numbers (e.g., [tex]M_4 < 29 < M_5[/tex]).

Nevertheless, Mersenne numbers are currently our best bet when it comes to finding increasingly larger prime numbers.

A key reason for this is that we have a computationally efficient deterministic primality testing algorithm. Namely, the Lucas–Lehmer test (LLT).

This algorithm is significantly faster than primality testing algorithms we have for general integers. So we can try increasingly larger values of n and determine, in reasonable amounts of time (given enough computational power), whether the corresponding Mersenne number [tex]M_n[/tex] is prime or not.

It turns out that n needs to be prime as well, in order for [tex]M_n[/tex] to be prime, which further reduces the pool of candidates we need to try to find a new Mersenne prime.

Mersenne numbers, by the way, take their name from Marin Mersenne, who astutely noticed that many prime numbers took the form [tex]2^n-1[/tex] (e.g., for n = 2, 3, 5, 7, 13, 17, 19, 31…).

Not being able to take advantage of a modern calculator (he published his findings in 1644), he didn’t get his list of exponents quite right, which in turn made his conjecture about prime numbers of the [tex]M_n[/tex] form for [tex]n <= 257[/tex] false.

He was wrong, but his mathematical curiosity paid off, leading us to two modern conjectures and today’s search for large primes.

Let’s be mathematically curious

I’m a big believer in mathematical curiosity. Asking, “what if” questions. Experimenting. This is why I’m so fond of experimental mathematics – despite its limitations and challenges.

As a kid, I used to spend hours trying to come up with proofs of Fermat’s Last Theorem and other unsolved problems. Obviously, those were seriously hard problems. I wasn’t going to prove anything.

But in the process of trying, I learned an incredible deal, developed a lifelong passion for mathematics, and even had the joy of discovering some (it turns out well known) simpler results on my own.

Plus one rather than minus one

As I came up with the idea of writing a post on Mersenne numbers, a “what if” came to my mind. What happens if we take numbers of the form:

[tex]\displaystyle C_n \equiv 2^n+1[/tex]

for n in [tex]\mathbb{N}[/tex]? What changes? Let’s find out.

Much like Mersenne did three century ago for his numbers, we can trivially see that some [tex]C_n[/tex] numbers are indeed prime. For example, without breaking out the calculator, we can instantly see that this holds for n = 0, 1, 2, 4, 8.

Obviously, [tex]C_n = M_n + 2[/tex]. In base-2, we went from a list of 1s (e.g., [tex]M_3 = 111_2[/tex]) to bookending zeros with two 1s (e.g., [tex]C_4 = 10001_2[/tex]). Still a palindromic, but no longer a repunit (a number comprised by only 1s).

It’s a small change, but we can already see that we have prime numbers for even values of n, whereas prime values of n where required for Mersenne numbers to be prime.

We also notice a certain pattern in the exponents above. We have 1, 2, 4, 8. With the exception of 0, all powers of 2. Hold on a second, there. The next number in the sequence appears to be 16. Let’s try that [tex]C_{16} = 65537[/tex].

Prime! Wouldn’t it be nice if the pattern held? We’d call them Cangiano primes and we would have arbitrarily large primes on demand. If only. 😀

Bad news, guys. [tex]C_{32} = 4294967297[/tex] is predictably not prime ([tex]641 \times 6700417[/tex]). Damn it, I had the perfect spot in my house already picked out for the Fields Medal. 😛

Now, I’m curious. Mersenne prime numbers are conjectured to be infinite, but increasingly sparse. What about, [tex]2^n + 1[/tex] prime numbers? Do they stop? Do they follow a similar distribution pattern?

Investigating Mersenne + 2 numbers

Time to help ourselves to modern technology. I wrote a script in Python to test whether other prime numbers in the form [tex]2^n + 1[/tex] exist.

I wanted the program to print both [tex]M_n[/tex] and [tex]C_n[/tex] prime numbers alongside for n below a maximum value provided in input.

It’s worth noting that we could narrow down the exponent to prime numbers only for [tex]M_n[/tex], but they wouldn’t work for [tex]C_n[/tex]. So a different list of exponent values would have to be used (primes for [tex]M_n[/tex] and regular integers for [tex]C_n[/tex]).

And since several Mersenne primes are known, you could also hard code them in the program instead.

At this initial exploratory stage, I didn’t really bother because, depending on results, I had a much more significant optimization in mind for [tex]C_n[/tex].

This is the initial Python script:

import sys
from gmpy2 import is_prime

def mersenne(max):
    return __prime_builder(max, lambda k: 2**k - 1)

def mersenne_plus_two(max):
    return __prime_builder(max, lambda k: 2**k + 1)

def __prime_builder(max, f):
    numbers = []
    for k in range(max):
        number = f(k)
        if is_prime(number):
            numbers.append((k, number))
    return numbers

if __name__ == "__main__":
    args = sys.argv[1:]

    if args:
        max_k = int(args.pop())
    else:
        max_k = 10000

    print("2^k - 1: ", mersenne(max_k))
    print("2^k + 1: ", mersenne_plus_two(max_k))

As an example, the output for [tex]n = 14[/tex] is:

$ python mersenne.py 14
2^k - 1:  [(2, 3), (3, 7), (5, 31), (7, 127), (13, 8191)]
2^k + 1:  [(0, 2), (1, 3), (2, 5), (4, 17), (8, 257)]

Each tuple includes the value of n and the value of [tex]2^n+1[/tex].

I checked all the numbers in this format up to [tex]2^{19,999}+1[/tex]. That’s a fairly large number (over 6,000 digits), but [tex]C_0, C_1, C_2, C_4, C_8, C_{16}[/tex] are still the only primes. Conversely, there were 24 Mersenne primes below [tex]2^{19,999}-1[/tex].

I didn’t believe that the n values being powers of 2 for known primes is a coincidence, so I wrote a version of the script that simply focuses on [tex]C_n[/tex] numbers with the following format:

[tex]\displaystyle 2^{2^k}+1[/tex]

import sys
from gmpy2 import is_prime

def mersenne_plus_two(max):
    numbers = []
    for k in range(max):
        n = 2**(2**k) + 1
        if is_prime(n):
            numbers.append((k, n))
    return numbers

if __name__ == "__main__":
    args = sys.argv[1:]

    if args:
        max_k = int(args.pop())
    else:
        max_k = 10

    print("2^2^k + 1 list:", mersenne_plus_two(max_k))

The now much quicker script failed to provide any prime number above [tex]65537[/tex] despite searching for numbers up to:

[tex]\displaystyle 2^{2^{19}}+1 = 2^{524,288}+1[/tex]

(Ignore the prompt saying 2^k + 1, instead of 2^2^k + 1. I didn’t change it before running the program.)

A conjecture emerges

Based on the – admittedly incomplete – evidence, I conjectured that:

I also believe that this conjecture will be extremely hard to prove.

Fermat’s primes

I did not, however, expect this to be a novel finding. So I searched the OEIS sequence database for the first 5 primes I found, and I came across A092506 which in turn linked to A019434.

The [tex]2^2^k + 1[/tex] subset ones that we considered at the end are known as Fermat’s primes. From there, with some research online, I was able to determine what we already know about them:

• No prime term larger than 65537 has been found.
• It is believed that there are no larger primes in that form.
• It’s fairly easy to prove that [tex]2^n+1[/tex] is only prime if it’s a Fermat number (so n has to be a power of 2).

With a feeling of validation, it was time to wrap it up. 🙂

Not before, though, writing on the joy of experimenting in mathematics, asking what if questions, and leveraging programming to explore math.