What Is: World's Largest Known Prime Number

miCRoSCoPiC^eaRthLinG

Mar 16 2005, 04:35 AM

Hi all,
[/tab] 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:

QUOTE

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.

[tab]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.

qwijibow

Mar 16 2005, 10:18 AM

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

Mar 16 2005, 01:22 PM

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

Mar 16 2005, 01:37 PM

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

Mar 16 2005, 01:47 PM

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

Mar 16 2005, 04:33 PM

QUOTE

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

Mar 20 2005, 01:05 PM

Doesn't anyone have a formula for working out the pattern of the prime numbers?!

If someone could find that then we wouldnt have this problem.

miCRoSCoPiC^eaRthLinG

Mar 21 2005, 05:52 AM

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

Mar 21 2005, 09:46 AM

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

Mar 23 2005, 06:47 PM

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:

CODE

// program 3.06 - Erasto
// by Giniu

#include <stdio.h>
#include <math.h>
#define SIZE 1000000

char 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...

Latest Entries

borlafu

Dec 28 2006, 11:22 PM

I don't think this is about human curiosity...

QUOTE

... running the Glucas program by Guillermo Ballester Valor of Granada, Spain.

The aim of this project is to find better numerical algorithms and to find where the limits of computer calculus is.

Maybe this problem has no direct or tangible objective, but it's a simple problem that makes cientists innovate and investigate to find tools to make easyer other tasks.

xboxrulz

Dec 28 2006, 10:18 PM

Interesting, maybe now we got to strap a bunch of Cell processor servers together and start finding more of these prime numbers.

xboxrulz

turbopowerdmaxsteel

Dec 28 2006, 05:53 PM

In my opinion the breaking of records such as these are a salute to our amazing development in the transistor world. Hard to imagine that not so long ago, we had only bulky vacuum tubes at our disposal.

seec77

Oct 3 2006, 05:23 PM

I don't think it's a quest for the largest prime number there is...
Sorry to be so rude, but you would think that people who coordinated such a large project are somewhat of mathematicians themselves, and even that is over-qualification for knowing there is no largest anything in mathematics. It's just a quest to keep on finding prime numbers that are higher than the largest one currently known. Of course this quest will never end. Each time that we reach a large prime number the one above it will take more computational power to find, but at the same time human technology will be progressing and will allow for that extra CPU speed. I tend to think that the time it takes to find each new prime number is pretty static.

I tend to think that this is a really useless distributed computing project. I mean, there are things much more valuable to do with those idle CPU cycles, such as finding the cure for cancer, solving some cryptographic riddles, or maybe something else. What will finding large prime numbers help humanity in? I am very supportive of curiosity, and I know that discovery of more and more numbers might actually lead to discoveries in other areas that will help humanity in the long-term, but the term is just too long for my taste.

Distributed computing is an important subject! We must all persuade ourselves and others to lend something that is of no value to us (spare CPU time) to the common good!

demolaynyc

Oct 3 2006, 04:09 PM

To me I think this project is so pointless. I don't even think there is a highest prime number in the world because numbers can go up to infinity. If the goal is to make up the highest prime number you can think of and win a prize, then that would be ok, but if you seriously try to look for the highest prime number there is--you're just simple stupid.