December 11, 2003
New Mersenne prime found

I love stories about big prime numbers.


More than 200,000 computers spent years looking for the largest known prime number. It turned up on Michigan State University graduate student Michael Shafer's off-the-shelf PC.

"It was just a matter of time," Shafer said.

The number is 6,320,430 digits long and would need 1,400 to 1,500 pages to write out. It is more than 2 million digits larger than the previous largest known prime number.

Shafer, 26, helped find the number as a volunteer on an eight-year-old project called the Great Internet Mersenne Prime Search.

Tens of thousands of people volunteered the use of their PCs in a worldwide project that harnessed the power of 211,000 computers, in effect creating a supercomputer capable of performing 9 trillion calculations per second. Participants could run the mathematical analysis program on their computers in the background, as they worked on other tasks.

Shafer ran an ordinary Dell computer in his office for 19 days until Nov. 17, when he glanced at the screen and saw "New Mersenne prime found."

A prime number is a positive number divisible only by itself and one: 2, 3, 5, 7 and so on. Mersenne primes are a special category, expressed as 2 to the "p" power minus 1, where "p" also is a prime number.

In the case of Shafer's discovery, it was 2 to the 20,996,011th power minus 1. The find was independently verified by other participants in the project.


Mersenne (pronounced mehr-SANE, named for a 17th century French monk/amateur mathematician Marin Mersenne, who was also a regular correspondent of Pierre Fermat) primes are cool, if you're into numbers. This page has some good history about Mersenne primes as well as some of the math surrounding them, such as the proof that if (2^p)-1 is prime, then p must be prime. The discovery of a new Mersenne prime also means that we have discovered a new perfect number, too.

There's an amusing story about Mersenne primes. Mersenne had originally postulated that the following numbers would lead to primes of the form (2^p)-1:

2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257

Mersenne himself was only able to verify this for numbers up to 19, though. Eventually, people began to determine that Mersenne had missed a few, and that he'd incorrectly included some others. The case of p=67 was resolved over 250 years after Mersenne's death.


This story is about the number 2^67-1, the 67th Mersenne number (numbers Mersenne had claimed to be prime), which was proven to be non-prime in 1903 by F.N.Cole (1861-1927). In the October meeting of the AMS, Cole announced a talk "On the Factorisation of Large Numbers".

He walked up to the blackboard without saying a word, calculated by hand the value of 2^67, carefully subtracted 1.

Then he multiplied two numbers (which were 193707721 and 761838257287).

Both results written on the blackboard were equal. Cole silently walked back to his seat, and this is said to be the first and only talk held during an AMS meeting where the audience applauded. There were no questions. It took Cole about 3 years, each Sunday, to find this factorisation, according to what he said.

This is freely quoted from E.T.Bell's book "Mathematics: Queen and Servant of Science", published in London, 1952; you can find the story in David Wells: "The Penguin Dictionary of Curious and Interesting Numbers" (Penguin Books, 1986)

For the curious: 2^67 -1 = 193707721 x 761838257287 = 147573952589676412927


That story was also told in a number theory textbook I had in college, though it said that Cole got the only standing ovation in AMS history and that it took him 20 years of Sundays, not three. Either way, I've always liked it.

By the way, the Great Internet Mersenne Prime Search (GIMPS) page is here. As with SETI@Home, you can loan your computer and its spare CPU time to the advancement of scientific knowledge.

UPDATE: Snarkout expands on the theme of big numbers and their allure. As always, well written and full of cool links. Check it out.

Posted by Charles Kuffner on December 11, 2003 to Technology, science, and math | TrackBack
Comments

My guess:
3 years of sundays
= 3 * 365
= 1095
= 7665 / 7
= 21 years

Posted by: Danil on December 11, 2003 3:23 PM

If you are interested in distributed computing and the search for prime numbers, Google the name "George F. Woltman." He is the leader of the effort. I happen to know that because he was my bridge partner for many years.

Posted by: dwight meredith on December 11, 2003 10:17 PM

If you are interested in distributed computing and the search for prime numbers, Google the name "George F. Woltman." He is the leader of the effort. I happen to know that because he was my bridge partner for many years. He was one very good bridge player (a number of high finishes in national events) and very good programmer but he work locating primes will make a mark that will last for ages.

Posted by: dwight meredith on December 11, 2003 10:18 PM

Were you on the math team at Stuyvesant or something?

Posted by: David in NY on December 12, 2003 11:26 AM

David, I did attend some Math Team meetings during my freshman year, but jazz band met at the same time, and that's what I did for the rest of my time at Stuy.

Posted by: Charles Kuffner on December 12, 2003 1:11 PM