The search for the largest prime numbers and GIMPS

t1-_d038-_le_pc3a8re_mersenne

Friends,

A few weeks back I started teaching my 11 year old son Python programming language. It is turning out to be an amazing experience as I see the delight on his face when his program works and when I see the worry when he is debugging a program that he thought he wrote “perfectly”. One of the programs that he recently wrote was to find the first n primes where n is a user specified value. When his programmed worked( after some debug), he asked me if we can run it long enough to be able to find the biggest prime ever discovered. A few years ago I had told him that there are prizes for finding the largest known prime number. He thought that he could win the prize by running his program overnight! That was an excellent starting point to discuss algorithms and why some algorithms are better than others. I also told him about the limits of a personal computer. We then searched on the internet for the prime number world records and how the largest prime numbers are found. And that is the subject of this VERITAS.

When scientists search for the largest primes, they focus on a special kind of primes known as Mersenne primes. First let’s talk about Mersenne numbers. A Mersenne number M(n) is a number of the form 2^n -1. In other words, a Mersenne number is one less than a power of 2. Note that I am writing 2 raised to power n as 2^n. Let’s calculate M(4). It is 2^4 -1 = 2X2X2X2 -1 = 15. So 15 is a Mersenne number. If a Mersenne number is a prime then we call it Mersenne Prime. Let’s take an example. M(3) is 2^3 -1 ie 7. So M(3) is a Mersenne Prime. The next Mersenne prime is M(5) which is 2 ^ 5 -1 = 2X2X2X2X2 -1 = 31. This is followed by M(7) ie 2^7 -1 = 127. At the time of writing this article 48 Mersenne primes are known.

Mersenne primes are named after Marin Mersenne, a 17th century French theologian, philosopher and mathematician. He was also a music theorist and is considered by many as the “father of acoustics”. In 1637 he published a book in which he described the laws governing the frequency of a stretched string. These laws are now known as Mersenne’s Laws. So Mersenne’s laws govern the sounds produced by musical instruments such as pianos, harps, guitars etc.

Marin Mersenne also edited the works of Euclid, Archimedes and many other ancient Greek methematicians. But perhaps his greatest contributions to the science and mathematics of that age was that he was a great connector of scientists and mathematicians. At that time, there we no scientific journals that people could read to know about the latest advances. All information exchange happened through people meeting each other or exchanging letters. Mersenne was at the centre of the scientific world and knew who was working on which problem. So if you wanted to know about the latest advances in the science of optics, for instance, you could ask Mersenne and he would tell you about the scientists working on that problem and may even introduce you to them.

Mersenne studied the primes which were later named after him. He found all Mersenne primes till M(31) ( i.e 2 ^31 -1). He actually suggested that M(67) and M(257) are also primes but that was later found to be incorrect. So we can say that Mersenne found Mersenne Primes till M(31). After that his list became inaccurate. M(31) was verified to be a prime in 1772 by Euler. Mersenne had also suggested that M(127) is a prime and that was verified by Lucas in 1876.

Now the question is: why is the search for the largest primes focused on Mersenne primes? There are two reasons for this: 1) We do not need to check every odd number one by one. We can just focus on powers of 2 ( and subtract 1) and may find some really big prime numbers. 2) There exist some very efficient and fast methods to check if a Mersenne number is prime or not. The Lucas-Lehmer test for primality of Mersenne primes is the one that most people use to search for large prime numbers.

In the 1940s and 50s mathematicians started using computers to search for Mersenne primes. Alan Turing and others used Manchester Mark 1 computer to search for these primes in 1949. The computer ran for nine hours but could not discover a new Mersenne Prime. The first Mersenne prime found by a computer was M(521) found by the SWAC computer running at University of California, LA in 1952. Humans just cannot compete with computers when it comes to complex calculations like these. This statement is borne out by the fact that this was the first prime to be discovered in 38 years. And then 2 hours later the computer found a new Mersenne prime : M(607)!

Before we go into the latest world records in the search for Mersenne primes, let’s discuss two very interesting theorems about Mersenne Primes. We won’t prove them. We will just list them to show how beautiful some mathematical theorems can be and how seemingly different mathematical ideas may have a deep connection.

1) Mersenne Primes and Perfect numbers are related: A perfect number is one whose proper factors( all factors except the number itself) add to make that number. One example is 6. It has 3 proper factors: 1, 2 and 3. And the sum of the factors( 3 + 2 +1) is 6. The next perfect number is 28. This is because the sum of its factors( 1 + 2 + 4 + 7+ 14) is 28. The interesting theorem is that a number can be a perfect number only if it is of the form 2^(n-1) X (2^n -1) and (2^n -1 ) is a prime. And we know that Mersenne primes are of the form 2^n -1. The converse theorem is that if 2^n -1 is a prime then 2^(n-1) X (2^n -1 ) has to be a perfect number. This is known as the Euclid-Euler Theorem. Note that 2^(n-1) is a even number since it is a power of two. So we can say that the search for Mersenne primes is equivalent to the search for even Perfect numbers! Mathematicians still do not know if there are any odd perfect numbers.

Another way to look at the Euclid-Euler theorem is that every Mersenne Prime is uniquely associated with a Perfect number. Let’s take an example: M(7) is a Mersenne Prime ie 2^7 -1 = 127 is a prime. So we can immediately say that (2^7 -1)X( 2^(7-1) is a perfect number. This number is 127 X 2^6 ie 8128 which is a perfect number. So if we find a Mersenne prime we also find a perfect number and vice versa.

2) A Mersenne number M(n) = 2^ n -1 can be a prime only if n is a prime. So, 2^7 -1 is a Mersenne prime and we know that 7 is a prime. We only need to check 2 to the power of primes when we search for Mersenne primes. That further simplifies our search.
We know that there are an infinite number of prime numbers- Euclid proved that in 300 BC! The number of Mersenne primes may also be infinite.

Today mathematicians use GIMPS ( The Great Internet Mersenne Prime Number Search) to search for large primes. This program was launched in 1996 and it uses the power of hundreds of computers of participants to find large Mersenne prime numbers. GIMPS was one of the first large scale distributed computing projects. The first success came in 1996 itself when the GIMPS program found that M(1398269) is a Mersenne Prime! This was a huge milestone because at that time it was the largest prime ever discovered- it has 420, 921 digits! Since that date GIMPS has kept breaking its own prime number world records. The 10 largest known prime numbers have all been found by GIMPS! The last prime discovered by GIMPS was in 2013- It is M(57, 885, 161) and has 17, 425, 170 digits! We have seen that when we search for new Mersenne numbers we also find perfect numbers. So, by finding the largest prime, GIMPS is also helping us find the largest perfect numbers. The largest perfect number, the one associated with M(57, 885, 161) has 34, 850, 340 digits! GIMPS shows us the power of distributed computing. The 10 largest prime numbers were discovered on normal PCs like yours and mine but that is because the task was distributed on many computers. You can also help find the next greatest prime( and there is a huge $ reward for that) if you participate in the GIMPS program ( go to http://www.mersenne.org/ to find out how you can join.)

Prime numbers have always fascinated us. They are like sparkling gems in the beautiful jungle of mathematics- amazingly beautiful but appearing magically without any pattern. The human mind continues to try and find a pattern in the appearance of primes. But we have been unsuccessful. So we entertain ourselves by finding larger and larger primes.

Let me end with a quote by Euler:

“Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.”

Kanwar

============= ============ =================== ============== ========= =====
Go wondrous creature, mount where science guides
go measure earth, weigh air, state the tides,
instruct the planets in what orbs to run
correct old time, regulate the sun
====== ======= =========== ============================== =============

( Image Source: Wikimedia Commons)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s