What Is: World's Largest Known Prime Number

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:


    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/1/hi/sci/tech/1693364.stm
3. http://www.mersenne.org/prime.htm

 

 

 

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

    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

 

 

 

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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:



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

Comment/Reply (w/o sign-up)