47th Mersenne Prime Confirmed

radiot88 writes to let us know that he heard a confirmation of the discovery of the 47th known Mersenne Prime on NPR's Science Friday (audio here). The new prime, 2^42,643,801 - 1, is actually smaller than the one discovered previously. It was "found by Odd Magnar Strindmo from Melhus, Norway. This prime is the second largest known prime number, a 'mere' 141,125 digits smaller than the Mersenne prime found last August. Odd is an IT professional whose computers have been working with GIMPS since 1996 testing over 1,400 candidates. This calculation took 29 days on a 3.0 GHz Intel Core2 processor. The prime was independently verified June 12th by Tony Reix of Bull SAS in Grenoble, France..."

Comments

Re:Cool processor

[Jarlsberg]

It was found through the GIMPS (The Great Internet Mersenne Prime Search). The site http://www.mersenne.org/prime.htm is currently down.

Odd's prime

[fph il quozientatore]

So, all primes greater than two are odd, but only one of them is Odd's!

Re:Odd's prime

[bcrowell]

His brother, Even Magnar Strindmo, is also an IT professional. Even, like his brother Odd, has been testing candidates since 1996. The latest candidate in Even's search was 2^42,643,801-2, which was found to be composite. The very next number, 2^42,643,801-1, was the one his brother found to be prime. "Yeah, it kind of hurts to get so close and not be the one who got it," admits Even, "but I gave it my best game. We agreed back in '96 that we'd split up the work and go even-odd. I guess it was just a matter of luck that he got the first prime. I'm going to keep on trying, though. He's ahead now, 1-0, but if we keep going, I figure at some point I'll pull ahead."

Re:Cool processor

[Kurusuki]

They're crunching 13-million-digit numbers with a desktop processor? Do they realize that they can put eight quad-core xeons in a machine and finish the calculation in a single shift instead of waiting a month?

I don't know about you, but the last 13 or so mersenne primes have been found using prime95 as a conduit for a mass distributed effort. I'm not sure where you live, but in most other places people can't just go out and put 8 quad-core xeons in a home machine.

Re:Cool processor

[JoshuaZ]

The system used for this is GIMPS, the Great Internet Mersenne Prime Search. The system uses a distributed computing system using unused computing power in personal computers to search for various candidate primes. Computers do one of two things: Either trying to factor candidate Mersenne numbers or running a Lucas-Lehmer test on candidates without any small prime factors (the Lucas-Lehmer test is a special primality test for Mersenne numbers that is very fast). They use modular arithmetic and a variant of the Fast Fourier Transform to handle the multiplications which might otherwise become too difficult. The procedure is naturally a problem that can be made into a parallel processing problem like this since there are so many different candidate numbers to look at.

The summary doesn't mention but it is worth noting that the Lucas-Lehmer test allows one to check the primality of Mersenne numbers (numbers of the form 2^p-1, p prime) much faster than you can test the primality of generic numbers (or almost any other specialized form). Thus, for most of the last hundred years the largest primes known have been Mersenne primes. Currently the largest known prime is a Mersenne prime and the next 4 largest are also Mersenne primes. The GIMPS website - http://mersenne.org/ has a lot more details of both the math and software and explains how you can join in to help the project.

Re:Cool processor

[Nutria]

I'm not sure where you live

He lives at home with his parents (or maybe in a dormitory room) and doesn't have a clue as to what it actually costs to run a home.

The joys of untested code

[tqft]

The admins missed the prime for about a month
http://mersenneforum.org/showthread.php?t=11996
Apparently the email that was supposed to be sent wasn't when the prime was reported

Re:Cool processor

[bergonom]

What are the odds this odd odd would be found by Odd?

Mersenne Primes correspond to Perfect Numbers

[JoshuaZ]

The historical reasons for caring about Mersenne Prime are twofold: First, Mersenne primes correspond to perfect numbers (numbers that are the sum of their positive less than the number. So for example, 6 has as proper divisors 1,2 and 3 and 1+2+3=6). The ancient Greeks were fascinated by perfect numbers but could not do much to understand them. Euclid showed that if one had a Mersenne prime one can construct an even perfect number. In particular, if 2^n-1 is prime then (2^n-1)*2^(n-1) is perfect. Almost 2000 years later, Euler showed that every even perfect number is of Euclid's form. Thus, investigating Mersenne primes tells us more about perfect numbers. The oldest unsolved problems in math are 1) are there any odd perfect numbers? and 2) are there infinitely many even perfect numbers? Thus, investigating Mersenne primes helps us get closer to solving one of the two oldest unsolved problems in mathematics.

Re:Cool processor - No, they can't

[rbarreira]

Actually that's not exactly correct, each iteration is also parallelizable. Most of the work in an iteration is a FFT, which is parallelizable.

http://www.fftw.org/parallel/parallel-fftw.html

It's less efficient to do this than using each core for one independent number, so it's only used if quick checking of a number is desired (for example, when double-checking a previously found prime number).