48th Mersenne Prime Computed
Written by Mike James   
Friday, 08 February 2013

Mersenne primes are easier to work with than general primes but the latest, the 48th known, has more than 17 million decimal digits - big by anyone's standards.

A Mersenne prime is of the form 2p-1 and until recently we only knew of 47 of them.

It can be shown that if p isn't itself a prime then 2p-1 can't be a prime, so some definitions include the condition that p is a prime. Certainly if you are looking for Mersenne primes you only need to test values of p that are prime. However, the problem isn't so much generating a possible Mersenne prime but in testing that it is a prime.

 

mersenneicon

Marin Mersenne 1588-1648

The first few values of the form 2p-1 i.e. 3,7,31,127 are easy to prove as being prime because you can check them using division but larger values of p quickly generate very big numbers that would take too long to check by attempting division by all possible factors.

The good news is that for a Mersenne prime there is a quick test called the Lucas–Lehmer primality test.

This states that 2p-1 with p prime is only itself a prime if it divides Mp-2 where Mp is generated from the series

Sk=S2k-1- 2

with S0=4.

As you can see this is much.easier task than testing all factors. In fact, it is so much easier than testing a general number for primality that the ten largest known primes are Mersenne primes.

The latest was found by Curtis Cooper, a mathematician at the University of Central Missouri. He revealed the 48th Mersenne prime to be 257,885,161−1 (a number with decimal 17,425,170 digits), as a result of a search executed by a GIMPS server network.

GIMPS, a distributed computing project designed to hunt for Mersenne primes, is also responsible for discovering the 10 largest Mersenne primes with the previous one, the 47th, being found in 2008.  The GIMPS software runs on around 1000 University computers and proving that the current find was prime took one machine 39 days of computation. The proof was then checked on a 32-core server in 6 days.

The discovery is eligible for the $3,000 prize from the GIMPS Project, but it isn't big enough for the Electronic Frontier Foundation's prizes of $150,000 and $250,000 to the discovery of the first prime with at least 100 million and a billion digits, respectively.

What is the point?

Well if you are a mathematician you don't need a "point" that other people would understand. But there is something strange about the way that you can take 2 and multiply it by itself a few times to get what has to be a very factorable number and then taking one away from the result changes the pattern so much that we have a prime with no factors.

It is also worth noting that, from a programming point of view, Mersenne primes are very simple. For example, in binary the first three are 11, 111, 11111 and so on.

In general 2p-1 is just a binary number with p ones. The fact that we have Mersenne primes for p=31, 61 and 127 is often a very useful fact when you need a big prime number quickly.

Finally, to prove that the 48th Mersenne prime isn't out of your reach Programming Praxis has a challenge and a solution for you - generate all 17 million plus digits. It turns out that simple C can't do it, but it is within the reach of the GNU Multiple Precision Arithmetic Library which gets there in a few minutes.

5 Trillion Digits of Pi - New world record

Yahoo! Gets to the 2 Quadrillionth bit of Pi - it's zero

60 trillionth binary digit of pi-squared calculated

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 

kotlin book

 

Comments




or email your comment to: comments@i-programmer.info

 

Banner


Paul Allen's Living Computers Sold For Record Prices
04/10/2024

Auction house Christie's of New York broke existing records for sales of rare and iconic computers when it sold the collection that the late Paul Allen, co-founder of Microsoft, had assembled to  [ ... ]



Watch The Oregon Programming Language Summer School Lectures
20/09/2024

Each year, the Oregon Programming Language Summer School covers topics in the foundations of programming languages. All the recordings of the lectures that took place during this year's event are now  [ ... ]


More News

 

Last Updated ( Wednesday, 20 January 2016 )