Student finds largest known prime number

DETROIT, Michigan (AP) --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 November 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 primes are rare but are critical to the branch of mathematics called number theory. That said, what is the practical significance of Shafer's number?

"People are going to make posters of it to hang up on the wall," said Shafer, who is pursuing a doctorate in chemical engineering. "It's a neat accomplishment, but it really doesn't have any applicability."

As for his own standing in the world of mathematics, "I don't think I'm going to be recognized as I go down the street or anything like that."

He said the method by which the number was found -- harnessing many computers together -- is more important than the number itself.

"Somebody else could have found the number," he said. "You install the program on the computer and it takes care of itself." But "I get the credit, along with the people that developed the software."



--------------------------------------------------------------------------------

Copyright 2003 The Associated Press. All rights reserved.


There is no passion to be found playing small, in settling for a life
that is less than the one you are capable of living. - Mandela

It's more of a technological feat than a mathematical feat, but computers are becoming more useful in mathematics, as they become more powerful.

They have proved useful to others in a research field that I sometimes work in, Classical Ramsey Numbers, although my own work in the area has been by hand so far. At some point I'd like to try to improve my upper bounds on R(3,3,3,3), the four color ramsey number, using a computer. Maybe even compute the number.

If I could compute the value, it would be only the second known multicolor Classical Ramsey Number. (I'm probably the only person who believes that it is possible.) The only other multicolor ("multicolor" means more than 2 colors) Classical Ramsey Number known is R(3,3,3).

Here is a picture of the two edge colorings associated with the three color ramsey number R(3,3,3). The pictures show that R(3,3,3)=17.

Plowshares Actions
The Nuclear Resister
School of the Americas Watch
miserable failure

Cauca, Colombia

quote:

---

Originally posted by ricardomath:

If I could compute the value, it would be only the second known multicolor Classical Ramsey Number.

---

Can you explain in lay terms what all that is?


There is no passion to be found playing small, in settling for a life
that is less than the one you are capable of living. - Mandela

First, we need the concept of a complete graph. To draw a complete graph, we first draw some dots (vertices) and then join each pair of vertices with a line (edge). Here are the complete graphs on 2, 3, 4, 5, 6, and 7 vertices.

Plowshares Actions
The Nuclear Resister
School of the Americas Watch
miserable failure

Cauca, Colombia

Given a complete graph on some number of vertices, what we are really interested is colorings of the edges. Notice that oin the above post, all of the edges of each graph are colored in black. Those are edge colorings with one color.

Below is an edge coloring of the complete graph on 10 vertices with two colors, red and blue.

The drawing to the right is the edge coloring. The left drawing shows only the red edges, and the middle drawing shows only the blue edges.

Plowshares Actions
The Nuclear Resister
School of the Americas Watch
miserable failure

Cauca, Colombia

Any three vertices of an edge coloring of a complete graph determines what we call a "triangle". That triangle has three edges. If all three edges are the same color, it is called (not too surprisingly) a monochromatic triangle.

Monochromatic triangles are what we seek to avoid when we color the edges of a graph.

In the post just above, is a picture of an edge coloring of a complete graph on 10 vertices, using two colors, red and blue. Note that the edge coloring depicted contains many monochromatic triangles. It contains triangles with three red edges, and triangles with three blue edges.

A fundamental technical definition is the following:

An edge coloring of a complete graph is called "good" provided that the it contains no monochromatic triangles.

Here is an example of a good edge coloring on 5 vertices, using two colors, green and orange:



Notice that there are triangles with two green edges and one orange edge. There are also triangles with one green edge and two orange edges.

But there are no triangles with three green edges, and there are likewise no triangles with three orange edges.

This is a good edge coloring on the complete graph on 5 vertices using two colors.

Now, look at the post just above this one. The fact that the (red and blue) edge coloring on 10 vertices in the above post contains monochromatic triangles is no accident. In fact, there is no good edge coloring (using two colors) on the complete graph with 10 vertices.

In fact, if you want to draw a good edge coloring on a complete graph, you can't have more than 5 vertices. The above (green and orange) good edge coloring, known as the pentagram coloring, is essentially the only way to do it on 5 vertices.

Just try to do it with 6 vertices, and you will see what I mean. It can't be done!

Plowshares Actions
The Nuclear Resister
School of the Americas Watch
miserable failure

Cauca, Colombia

[This message was edited by ricardomath on December 12, 2003 at 03:45 PM.]

[This message was edited by ricardomath on December 12, 2003 at 03:49 PM.]

quote:

---

Originally posted by ricardomath:
Any three vertices of an edge.......

---

thanks, I was debating on whether I wanted to teach math or history and you have made my decision easy

Don't be too discouraged. This is research level mathematics.

It would be alot easier to explain in person, with a blackboard and colored chalk. Or even if I had ready made pictures. I have a few that I've made for a paper of mine, including the picture in my first post, but I've had to rely on searching the web for the others.

It's not as bad as it looks, though. In fact, I've sometimes wondered if it could be appealing to high school kids, and even elementary school children. Sort of a hands on mathematical exploration. Give them some drawings of complete graphs of various sizes, and challenge them to color the edges, while avoiding monochromatic triangles.

For example, with 3 colors, the largest you can color is 16 vertices (the two colorings in my first post). But how high could high school kids get?

My work involves the same question with 4 colors. In the 1970's, Fan Chung managed to do 50 vertices. It is easy to see that 65 is too high.

My result in the area was to prove that you couldn't do it with more than 61 vertices. So far, that's the best known upper bound for 4 colors.

Plowshares Actions
The Nuclear Resister
School of the Americas Watch
miserable failure

Cauca, Colombia