What Is: World's Largest Known Prime Number

[miCRoSCoPiC^eaRthLinG 0]

Hi all,

I just came across this while searching for some mathematical principles. Do you know that there's this foundation named Great Internet Mersenne Prime Search (GIMPS) whose sole work is to search for the largest prime number known to man ? Every couple of years they come up with a new number only to beat their earlier score. The last one found and the largest currently known prime, 2^24036583 â 1, was found by Josh Findley through the GIMPS project on May 15, 2004. It is 7,235,733 digits long, almost one million digits more than the previous record holder.

 

Here's a direct quote from the InfoPlease.Com site:

Euclid proved in the 3rd century BC that there are an infinite number of prime numbers. A prime number can be divided only by itself and the number 1. Primes serve as the building blocks for all positive integers, and have applications in cryptography and other fields.

 

Mersenne numbers are numbers that are one less than a power of two (2^n â 1). A Mersenne number that is also a prime number is called a Mersenne prime. These can be found and verified relatively quickly. Before 1952, 12 Mersenne primes were known; with the aid of computers, 29 more have been found. The seven largest have all been found by the Great Internet Mersenne Prime Search (GIMPS), a distributed network of volunteers using their spare computer power to find the largest Mersenne primes.

 

The largest currently known prime, 2^24036583 â 1, was found by Josh Findley through the GIMPS project on May 15, 2004. It is 7,235,733 digits long, almost one million digits more than the previous record holder. The Electronic Frontier Foundation is offering a $100,000 award to whomever is the first to find a prime number with at least ten million digits; it seems likely that this will be claimed within the next few years.

As you can see there's a very lucrative prize waiting for you if YOU happen to be the one with the new Prime in the block.

 

Read more about it at:

1. http://www.infoplease.com/ipa/A0920820.html

2. http://news.bbc.co.uk/2/hi/science/nature/1693364.stm

3. http://www.mersenne.org/primes/

[qwijibow 0]

Great...So all i need now, is several hundred old computers, use OpenMOSIX to constuct a cluster computer, and getmyself that 100,000 that with any luck, might just about ocver my electricity bill.

[miCRoSCoPiC^eaRthLinG 0]

Hehehe... it won't take that much. Just make a cluster of the brand new p4's or alikes (10 would be good I guess) and be out on the hunt... I wonder though what kind of equipment it takes to perform such intense number crunching operations (other than supercomps of course).. Do you know of any site that guides you or at least provides the basic specs for such a job ?? It's worth a try - $100,000 is no mean joke - though no conventional Data Type can handle those numbers. So you got to come up with your own code capable of handling 32-64-128 (whatever) bit integers in order to deal with such immense numbers.

[qwijibow 0]

There are libraries in C which are designed to allow you to use data types of any length. for example you could define a float data type that uses 1000 bytes, then use it to divide 10 by 3.but these large data types have to be calculated by an emulated cpu that wil not approximate divisions like x86's do, which is slower.I think a cluster computer would be perfect for this type of number crunching.Because the search can easily be forked() into simultanius porcesses that do not need to compunicate to function.to stand a good chance of winning, you would need to clock up more computing power for hours than all the other ocntestants put together, i dont think 100 p4's would do it

[miCRoSCoPiC^eaRthLinG 0]

100 P4s - you'd get one for approx. THB 22, 000 here.. that's about $550 - times 100 = $55,000 ... yeah you're quite right - just the hardware setup alone (include a couple of extremely high performance switches)..would go way way above the prize money.. How about the concept of distributed internet computing - that might cut down the setup cost - but then you've to depend of ppl volunteering and downloading your client.. lot of hassle. Hrrrrmmmppphhh.. What wouldn't I give to have a setup like that though.

[qwijibow 0]

How about the concept of distributed internet computing

lol, yea thats what they are doing.by downloading and running their software, you are voulenteering your spare cpu power.
but the cash goes to the machine that made the discovery.

so although its a joint effort the prize money is trying to encourage you to volenteer as much computing power as possable to increace your chances of winning.

[musichere 0]

Doesn't anyone have a formula for working out the pattern of the prime numbers?! :DIf someone could find that then we wouldnt have this problem.

[miCRoSCoPiC^eaRthLinG 0]

I'm sure there are such formula's in existance. The simplest approach would be to apply the rules of divisibility on each successive integer from the set of whole numbers. The main problem is that for any integer 'n' you've to check whether it's divisible by any of the numbers: 2...(n-1) ... Here's an routine written in VB that generates an array of primes till a number 'n' that you specify.... Get it Here.

But if you study the routine a little bit, you'll notice how fast we'll run out of stack/memory space as we go for higher and higher numbers. The standard integer/double data types aren't sufficient at all - in such a case you'll have to create your own high capacity data types to hold these humongous primes. As qwiji pointed out there are some C based libraries that aid you in designing such data types, but you'll need to be fairly advanced in Mathematics to be able to makes sense of them in any way

[Xeon 0]

Wow, that's pretty interesting. It's a good thing that the largest prime number happens to be a Mersenne Prime, otherwise it would be so long you couldn't even write it down.

[Giniu 0]

Hi... what I know from my "theoretical math" study, the most efficent way to find prime numbers is Sieve of Eratosthenes. It gives you chance to get them counted very fast, and memeory usage is one bit per prime number, so this can be it... I will post there small code (maybe wrong, couse i'm mathematician, but I tested it with gcc... remember add math library when compiling, you should also add optimalistation - like this:

gcc -O2 test.c -o test.o -lm

this method works fine and result of:

time test.o

is something about 0.001 ms for all prime numbers from 0 to 100000 - this is limit of this example and my coding knowledge ), I can give you some rules and theory, so if know some language, you would be for sure able to build it yourself... so let's start:

 

First of all we are generating methods to store information, we are using table of long long integer, since we need many bits with possible less indexes (in example I used char...), and creating few functions that will put 0 or 1 to bit represented by number (prime, or not prime) and read value of bit that represents it, then we need to put that values:

 

number 0 - value 0

number 1 - value 0

other - as far as we can - value 1

 

when we have this ready, the main generating function...

 

we are taking first number that have value of 1, but is before sqrt of largest possible number, lets call it p like prime and we are putting 0 to all numbers that looks like a*p, where a=2,3,4,... till end of all numbers, then we are taking first number that have value of 1...

 

this is how you can do it with C:

 

// program 3.06 - Erasto// by Giniu#include <stdio.h>#include <math.h>#define SIZE 1000000char erasto[(int)(SIZE/8)];void putErasto(int number) {	int position, inside;	char value;	position=number/8;	inside=number%8;	value=(1 << inside);	erasto[position]|=value;}void delErasto(int number) {	int position, inside;	char value;	position=number/8;	inside=number%8;	value=~(1 << inside);	erasto[position]&=value;}char checkErasto(int number) {	int position, inside;	char value;		position=number/8;	inside=number%8;	value=(1 << inside);	if ((erasto[position]&value)!=0) {  return 1;	} else {  return 0;	}}void clearErasto(void) {	int flow;	for (flow=2; flow<=SIZE; flow++) {  putErasto(flow);	}	delErasto(0);	delErasto(1);}void countErasto(void) {	int flow1, flow2, countTo;	clearErasto();	countTo=sqrt(SIZE);	flow1=2;	while (flow1<=countTo) {  flow2=flow1*2;  while (flow2<=SIZE) { 	 delErasto(flow2); 	 flow2+=flow1;  }  flow1++;  while ((flow1<=countTo)&&(checkErasto(flow1)==0)) { 	 flow1++;  }	}}char isPrime(int number) {	return !checkErasto(number);}int main(void) {	countErasto();	//there what you need... just like:	printf("\n\n 123123 is");	if (isPrime(123123)) printf("n't");	printf(" prime number,\n");	printf(" but 7 is");	if (isPrime(7)) printf("n't");	printf(" prime number.\n\n");}

This maybe isn't best example, but how I said I'm mathematician not a coder, so this is only viewing of an idea... I tried as much as I could... just try it and remember - it always takes same time - to generate sieve of given size... hope this will help

 

Giniu

 

edit-----------------

oh, and this example was made on "introduction to math in algorythmic", thats why 3.6 - list 3 exercise 6 - havent time to change this... and: "You can copy and do with it whatever you want, as long as you left line: // by Giniu at top of this, you can add something like orginal version or whatever... I don't realy care... just left autor...

[sparkliestars11 0]

wow i thought there weren't any limit to numbers

[nakulgupta 0]

Well theres one thing that i picked up in school...Consider a prime number say 'n'(>6). Then (n+1) or (n-1) is divisible by six. Its converse need not be true. Now i dont know how this can be converted into code..I absolutely suk at computer languages(Never learnt one actually).

[spickid101 0]

holy! thats alot for numbers!!!!!! awwwwwwwwww my head hurts!

[Antnydude47 0]

woah thats a crazy number....why do these people bother doing this kind of stuff???

[miCRoSCoPiC^eaRthLinG 0]

woah thats a crazy number....why do these people bother doing this kind of stuff???

Human killer curiosity and the Noble quest for knowledge put together

Update on this:

On December 15, 2005, Dr. Curtis Cooper and Dr. Steven Boone, professors at Central Missouri State University, discovered the 43rd Mersenne Prime, 230,402,457-1. The CMSU team is the most prolific contributor to the GIMPS project. The discovery is the largest known prime number.
The new prime is 9,152,052 digits long. This means the Electronic Frontier Foundation $100,000 award for the discovery of the first 10 million digit prime is still up for grabs! The new prime was independently verified in 5 days by Tony Reix of Bull S.A. in Grenoble, France using 16 Itanium2 1.5 GHz CPUs of a Bull NovaScale 6160 HPC at Bull Grenoble Research Center, running the Glucas program by Guillermo Ballester Valor of Granada, Spain.

Dr. Cooper joined GIMPS over 7 years ago with colleague Dr. Vince Edmondson. Edmondson was instrumental in the campus-wide effort until he passed away in 2003. Cooper, Boone, and CMSU truly earned this discovery, diligently coordinating over 700 PCs!

Source: http://www.mersenne.org/