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.
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.
Comments
or email your comment to: comments@i-programmer.info
|
Last Updated ( Wednesday, 20 January 2016 ) |