New Possible Record Prime Number Found

An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS), a distributed computing project, has probably found a new record prime number. Two verification runs have started; no errors were found in the initial calculation. The number of primes found lately, four in just over two years, is higher than previously expected. This prime is just under 10 million digits, which means that one of the participants in the project makes a good chance to obtain his or her part of the EFF prize of $100,000 for the first prime of over 10 million digits in the coming months. In 2000, one of the Gimps participants collected the $50,000 reward offered."

Comments

/.ed

[dascandy]

Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage? Jeez... where are your priorities?

Re:/.ed

[meringuoid]

Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage?

Ah, but... a number of ten million digits? That has to take up ~ 10MB of disk space. And now the link's been posted to /., where every lunatic is now clicking on it and thinking that by some bizarre geek savant superpower they're going to somehow look at it and go 'yup, that's prime all right' or something...

No wonder the server's a smoking crater now :)

Re:/.ed

[stunt_penguin]

Aha 10 million digits may be easy to store, but deviding that number by other number lower than half that number to prove it is actually a prime number isn't really that easy.

I assume (hope)there are other ways of proving primeness than brute forcing it by doing lots of divisions of series' of incredibly large numbers just to find the one that won't devide evenly.

Re:/.ed

[dascandy]

Finding common divisors is usually done with the formula of Euclides. That brings it down to iirc the log of the number, which is just 10000000.

A very good (but not perfect) sieve for primes with no false negatives is the Lucas-Lehmer primality test. I expect them to use that for first selection runs.

For a full certainty, the only cause (I think) you have is to repetitively try to divide it by another and figuring out you keep stuff left. I am quite certain they're using distributed computing for that.

Re:/.ed

[tie_guy_matt]

10MB of disk space? No problem just gzip the file ... oh no wait never mind!

Re:/.ed

[dascandy]

Well... the server is at mersenne.org. I somehow expect them to have found a mersenne prime, which with 10 million digits takes about 15 bytes to store in plain-text, and only 4 if you store it efficiently:

2^35000000-1 => that's in normal form. You only have to store the exponent, the rest is constant. Since it's smaller than 4294967296 you can store it in a normal int (4 bytes), and since it's larger than 16777216 you can't store it in 3 bytes.

Re:/.ed

[meringuoid]

Aha 10 million digits may be easy to store, but deviding that number by other number lower than half that number to prove it is actually a prime number isn't really that easy.

When you're brute-forcing your way to a test for primality of n, you needn't go all the way to n / 2, only up to sqrt(n). If xy = n, and x > sqrt(n), then you should have found the factor y already.

I think there are also more efficient tests that can determine whether a number is prime to arbitrary probability without trying every possible divisor; not my field of expertise, though. Inquire of Google for isprime algorithms.

Re:/.ed

[moro_666]

Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage? Jeez... where are your priorities?


  Next slashdot news will be how slashdotters managed to wreck the hard disk in the server that contained the 10 million digit prime :p
Now that would be real ./ing power.

  I think it's kindof annoying to install that distributed computing software everywhere where you'd like to use the spare cpu time. My homies mess up their windows machine so often that i've stopped trying to keep anything running there (a machine online 24/7 that shows a web browser and msn for 3-4 hours a day, what a waste).

  Can't they put it in applets that i can run from their webpages ? Surely Java is a bit slower than C in algebra (not really as much as you think, on very simple math tests the difference was about 10-20% last time i measured), so a C client should be available, but a web based client which i can just run in any java enabled browser would definitely increase the userbase.

Re:/.ed

[shippo]

Indeed. The test performed to check that a Mersenne number is prime consists of repeated squaring, followed by the addition of an offset, using modular arithmetic. The number of iterations of the algorithm is equal to the value of the exponent of 2. If the final result is zero, the number is prime.

This only works due to the Mersenne prime being one less than a number with many known factors.

Re:/.ed

[Xylaan]

I used to participate in the project while I was in college.

They use a distributed Lucas-Lehmer Test. This takes days to weeks depending on the computer. However, given the possibily of either implementation bugs or some sort of minor rounding error in the vast amounts of floating point operations being performed (and since it's iterative, if an error occurs early in the run, it could propagate to something large by the end), they do independant verification on any number that's found.

In addition, if you have slower computers, you can elect (or will be assigned) factoring work, which is simply to do first-pass factoring (again, up to a limit to reduce the number of things that have to be tested) on numbers. Any number you can't find a factor for will be flagged as 'factored', and will eventually be scheduled for a LL test.

Re:/.ed

[dascandy]

The point behind a mersenne prime is that, in binary, it's always like this:

111111111111111111.................111111111111111 1

They differ only in the number of ones. The point why they are mersenne primes is BECAUSE they have this property. Since these numbers are relatively often prime, it's a lame (*cough*, ok, cheap) way to get to very large prime numbers.

So, all you have to store to know the number is the number of binary digits. Conveniently, that's the exponent in power-of-2 notation.

You can write down the exponent in 4 bytes, I sure hope. If you want to type it out in notepad, try using the notation I provided. It fits in 15 bytes with ease.

Re:/.ed

[vidarh]

You can certainly reduce the number of tests quite dramatically. Someone else pointed out that you only need to check up to the square root.

Of course, if you do know all preceeding primes, then it's just a matter of restricting your test to just that sequence, as everything else by definition have smaller prime factors you'll test against.

If not there's a bit more work, but you can still save a lot over brute forcing it.

If you start at 2 and work your way upward, and for as long as you know the next prime up, you'd only need to test with the next prime.

After that, you can still discard tests with any numbers that can trivially easily be shown to have small prime factors without even trying a division, like all even numbers, all numbers ending in 5 etc.. There are quite a few rules that can be added to just immediately skip a lot of numbers as you're iterating upwards with quite cheap logic.

You can also test the number you will use to test your potential prime by first testing that against a set of small primes (apart from the ones you've already discounted by not generating the test numbers), to quickly discard those test numbers before you attempt a huge expensive division. It's also possible to derive relatively simple rules to check for divisibility of many small primes that may be far cheaper than trying an actual division once you start getting up to reasonably large numbers.

The method of discaring tests against numbers divisible by a set of small primes is known as the Sieve of Eratosthenes... I think there are a few alternative methods - the main benefit of the sieve of Eratosthenes is that the basic algorithm extremely simple and still a vast improvement over brute forcing.

Re:/.ed

[PhraudulentOne]

Indeed. The test performed to check that a Mersenne number is prime consists of repeated squaring, followed by the addition of an offset, using modular arithmetic. The number of iterations of the algorithm is equal to the value of the exponent of 2. If the final result is zero, the number is prime.

This only works due to the Mersenne prime being one less than a number with many known factors.

Lemme guess, your a real hit with the ladies, eh?

Re:/.ed

[Anonymous Coward]

your a real hit with the ladies, eh?

_you're_ virgin, eh?

NB, that is not a possessive dig. Good spellers always get the babes.

Re:/.ed

[Anonymous Coward]

Surely Java is a bit slower than C in algebra (not really as much as you think, on very simple math tests the difference was about 10-20% last time i measured), so a C client should be available, but a web based client which i can just run in any java enabled browser would definitely increase the userbase.

This is actually very untrue, especially in the case of GIMPS. The C code to do the Lucas-Lehmer test has been coded so efficiently that you would be lucky to get 50% performance reduction using Java.

I have used GMP in C to make my own version of this program that would run over a Linux cluster but the performance is so much slower that I pretty much gave up. (Note: that is highly-optimized C using the GMP linux library)

How a java applet using Bignum would fair? Very very poorly. These are general math routines that have not been optimized for the program (let alone processor) which is the exact opposite in the case of GIMPS.

Java really isn't the catch-all of programming languages. It is meant to be an applet language not a high-performance computing language. If you want highperformance learn Fortran or C...

Re:/.ed

[BamZyth]

Two geeks at the university bar WC: -"My prime is bigger than yours"

Re:/.ed

[Anonymous Coward]

Mersenne Numbers (numbers of the form 2^n -1 which as you say are 111.111 in binary) are not relatively often prime...

There are only 42 confirmed mersenne primes, the largest being 2 ^ 225,964,951-1...

So only 42 out of 225,964,951+ are prime... relatively infrequent I would say :P

Re:/.ed

[dascandy]

You just get more when rooting with a larger prime... Formulae like big primes...

(cleverly avoiding girl jokes by completely forgetting about them)

Re:/.ed

[smartdreamer]

Makes me wonder what's the point to find such prime numbers? Right now, it looks like "mine is bigger than yours" : pointless.

Re:/.ed

[Anonymous Monkey]

My wife is currently teaching prime numbers at school, so we talk a lot about them over the dinner table.(geek maries geek and talks about math over candle light, weird.) Anyway, the Eratosthenes method you discuss would take a lot of useless calculations out of the mix. The following links will explain it better than I can.

http://www.math.utah.edu/~alfeld/Eratosthenes.html

and http://mathforum.org/dr.math/faq/faq.divisibleto50 .html

Re:/.ed

[grumpyman]

They differ only in the number of ones. The point why they are mersenne primes is BECAUSE they have this property. Since these numbers are relatively often prime, it's a lame (*cough*, ok, cheap) way to get to very large prime numbers.

I've got a larger prime here: 1111111...111 (1 google google google times). Ok now go verify this!!

Re:/.ed

[Anonymous Coward]

Unfortunately, Mersenne primes are not the only primes. They are just easier to find. So we don't necessarily know the entire sequence of prime numbers up to any one number that high.

Re:/.ed

[AaronCampbell]

It gets better than that. A Mersenne Prime is a prime number that is one less than a power of 2 (like 3=4-1=2^2-1 and 7=81=2^31). Given this: M_n=2^n-1, you also know that for M_n to be a Mersenne Prime, n must be prime. So you don't even do calculations for the rest of the numbers. Read the whole snippet for more info.

Re:/.ed

[eepok]

That is a fantastic piece of information now permanently stored in my brain. Thank you for making my day a little brighter. =)

Re:/.ed

[yali]

That has to take up ~ 10MB of disk space.

Can't they just compress it?

Re:/.ed

[Anonymous Coward]

There are only 42 confirmed mersenne primes, the largest being 2 ^ 225,964,951-1

Did you smoke crack this morning? You are off by 200,000,000 on that exponent. The 42nd confirmed is is 2^ 25,964,951-1.

Re:/.ed

[mightypenguin]

Just because the number is prime does not mean that it does not have repeating sequences inside of it. Those could easily be compressed, though with data like that I'm not sure if it would be worth it.

Re:/.ed

[rolandog]

you've just increased some geek's hope that he'll find a prime by about 7.7 times

Re:/.ed

[Anonymous Coward]

The point behind a mersenne prime is that, in binary, it's always like this:

111111111111111111.................111111111111111 1

I prefer the more compact hex notation [F|7|3|1]FFFFFFF...FFFFFFFF

Extra bonus for the first to come up with an f(x) to tell what the first hex digit is.

Re:/.ed

[Anonymous Coward]

Makes me wonder what's the point to find such prime numbers?

They give and explanation for that here.

Re:/.ed

[moro_666]

java is the only thing that works safely through any web browser.

you can't run C or Fortran by clicking on a web link, such an alternative would be a great boost to the distributed computing stuff (it is meant as an alternative to C and Fortran, not as a replacement). Besides, if java's algebra is even 10 times faster then 10 000 users on te web still mean an extra 1000 machine power. And you'll have more than 10 000 users running this.

I never claimed java is that one-does-it-all, but it's the only thing that you can run in a webbrowser and has sufficient portability and performance (flash is a no-no and javascript isn't even worth mentioning). Currently that is just an unused resource.


It is meant to be an applet language not a high-performance computing language.


  Applet language ? Are you sure ? Because i'd rather think it's an ideal platform that has the almost perfect OOP implementation and the most stable threading system i've ever seen. Not to mention the independance from the server operating system and hardware. I must warn all the banks and other big server owners around in my country that their J2EE applications are actually running it all in an "applet language" :p

  If i were you, i'd forget that applet sentence and get a book to read about what you really can do with Java :p

Re:/.ed

[smartdreamer]

Thanks for the link.

Their is a couple explanations there, but none of them gives a good reason. Thet are

• Tradition Tradition as never been a real reason to continue something ; only what inspired the tradition could.
• For the by-products of the quest Comparing prim computation with space odessy is a little bit exagerated. The FFT trick, for example, as also been found in other area.
• People collect rare and beautiful items Laughable. You cannot try to establish a comparison with fundamental scientific quest and put it side by side with this "argument". And I did't know that inifinit abstractions are rare.
• For the glory Glory as to come from acheivement, and this what am I looking for here.
• To test the hardware Like it was the only or the best hardware test. Sure you can compare (in a limited view) computer speed with a prim computation test. But, do we need bigger prims number? I think not.
• To learn more about their distribution Unless you can't compute every numbers, you don't bring anything worth to mathematics because their is enough data now. What we miss is a theory.
• For the Challenge Let say it is similar to "for glory". Everything can be done "for the challenge".
• For the Money Ah! There we are : money. But the question I raised was to find a purpose to this "quest" and to find out why somebody would give money to such thing. So this would be a circular reasoning.

So to resume this, could I say it is a tradition taken from dead people they transformed into a "challenge" for glory justified by money and addressed to "people who likes to collect rare (infinite) things" and supposedly meant to help without knowing how except for the by-products of the quest?

Sorry, I'm sceptical today...

Re:/.ed

[dascandy]

That's not prime. Its an even number of ones, which is trivially breakable into:

111111111.................11111111 (5*10^299 ones) * 100000......00000001 (with 5*10^299 - 1 zeroes).

Do I get a nobel prize now?

Re:/.ed

[Anonymous Coward]

only 10 characters are used in the file, of course it will shrink by at least 50%

Re:/.ed

[dascandy]

Want another? A number that could be a mersenne prime cannot be one if the exponent isn't a prime also.

Proof: For every number with a non-prime exponent E, take two possible factors that compose E as K and F. Now:

11111...111 (F 1's behind each other) times 10000...(F-1 zeroes)...000010000...(F-1 zeroes)...000010000...(F-1 zeroes)...000001 with K-1 times the repeat (and thus K ones) will equal the candidate number.

You can also prove it more mathematically:

sum from (I = 0) to (K-1) over (2^F-1) * 2^(I*F)
Written out, the series goes:
= (2^F-1) * 2^0 + (2^F-1) * 2^F ...
= (2^F-1) * 1 + 2^2F - 2^F ...
= 2^F - 1 + 2^2F - 2^F ...
= 2^2F - 1 ...
= 2^(F*K)
= 2^E

Hope you enjoyed it ;)

Re:/.ed

[dascandy]

For the record, example:

2^15-1 is composite, because 15 is composite:

15 = 3 * 5

2^15-1 = 111111111111111 binary, equals 11111 * 10000100001, equals 111 * 1001001001001. In decimal, that's 32767 = 31 * 1057 = 7 * 4681.

Re:/.ed

[Phleg]

Actually, it's pretty easy to compress Mersenne primes. Due to their form (2^n - 1), their binary representation is a simple string of n 1's.

10 million?

[Walterk]

Is that all? It'll be real news when it's 42 million.

Re:10 million?

[meringuoid]

42 million? How unimaginative. Personally, I'd like to see a huge prime with a prime number of digits...

Re:10 million?

[BarryNorton]

Personally, I'd like to see a huge prime with a prime number of digits

SB8, the largest non-Mersenne prime currently known, has 2759677 digits (which is prime).

Re:10 million?

[MasamuneXGP]

Fail at recognizing the meaning of existance.

Re:10 million?

[ComaVN]

Preferably in a prime base, instead of the unimaginative base 10

Re:10 million?

[EntropyEngine]

Can someone explain to me why any of this matters?

Is this just more number nerdery, or is there a practical application for such vast and unfathomable numbers?

Re:10 million?

[BlowChunx]

Wouldn't that just be 1?

At least it would be if I get to pick the base after I found the prime number...

Re:10 million?

[SComps]

I have to agree with you there. I'm reading through this thread and saying to myself "Ok, so this is cool; but how is this going to help me in my day to day life?"

Re:10 million?

[BarryNorton]

No... that's not a prime number of digits.

Re:10 million?

[markov_chain]

SB8, the largest non-Mersenne prime currently known, has 2759677 digits (which is prime).

Moreover, 2759677 has 7 digits, which is prime too! How fun.

Re:10 million?

[geegs]

Write it in binary. That way every Mersenne prime will have a prime number of digits because (2^p - 1) divides (2^(pq) - 1)

Re:10 million?

[BarryNorton]

Our comment numbers, 14297779 and 14298043, are also both prime...

Re:10 million?

[llamaguy]

Yep. You know those fancy encryption schemes that stop the evil criminal soviet fraudsters stealing your credit card numbers? They're based on the fact that, while finding out the product of two primes is easy, finding those two primes again from the given product is harder than it looks for big primes. A 'public key' is the product of two suitably large primes, and a 'private key' is those two primes.

Of course, we're still only on 256-bit encryption right now. Should be a while until however-many-bits-this-prime-needs-bit encryption will pass into common use.

Re:10 million?

[madshot]

Personally, I'd like to see a huge prime with a prime number of digits...

Spoken like a true geek... welcome to the club!!!

Re:10 million?

[certel]

I was thinking the same thing. Maybe they could use the computers for other things, such as gene mapping and quit giving away thousands of dollars for something like this.

Re:10 million?

[pjt33]

For a large prime P the odds are pretty good* that there's an prime Q such that sqrt(P) < Q < P. That's equivalent to Q < P < Q^2, so P base Q has 2 digits.

* I'd say 1, but after 30 seconds' thought I haven't found a trivial proof.

Re:10 million?

[Metasquares]

You can get a new perfect number out of this (2^(n-1) * (2^n)-1), but other than that, there's not much point. Maybe cryptography.

Re:10 million?

[penguinoid]

Actually, *all* mersenne primes have a prime number of digits.

Re:10 million?

[ComaVN]

Not in base 10, they don't

Re:10 million?

[CastrTroy]

But this really doesn't help at all in cryptography. So we can spend thousands of computing hours finding big primes with known algorithms. What we really need would either be new algorithms which could find large primes as this, or a new algorithm to factor large primes in order to defeat encryption. Another thought is, what use for encryption is using large primes such as these. If we decide we are now using 1,000,000 bit primes for encryption, because we have an easy way of finding them, then maybe encryption would be easier to break. As the size of the prime number gets bigger, the number of primes of that size also decrease. If we are using primes so big, that there are only 100 prime number to use of that size, couldn't they just figure out all the possible numbers that are products of those primes, by multiplying each prime by each of the other primes? It probably wouldn't take much to multiply 100 numbers by 99 other numbers, no matter how big the numbers were.

Re:10 million?

[pomakis]

Hello?!? Where's 2*2*3*75011 when his infamous postings would finally be relevant?!?

Re:10 million?

[BarryNorton]

I'd imagine all of these numbers with no factors make his head hurt...

Re:10 million?

[Sir Codelot]

Personally, I'd like to see a huge prime with a prime number of digits...

Prime number of digits when expressed in which base?

;)

Re:10 million?

[Anonymous Coward]

Moreover, 7 has 1 digit, which is prime too! How fun.

Re:10 million?

[sfontain]

Moreover, 2759677 has 7 digits, which is prime too! How fun.

The word "seven" has 5 letters, which is prime too! And if you subtract 2 from 5, you get 3, which is also prime!

Re:10 million?

[Sir Mac Gyver]

And 7 has 1 digit, which is also prime!

Re:10 million?

[StikyPad]

And 7 has 1 digit, which is ALSO prime!

(And not to brag, but I solved that one in my head.)

Re:10 million?

[cagle_.25]

...and if you add up all of the values of the letters in "Mersenne" according to our special letter codes, you get ... 1995. That's right, for just $19.95, you too can own a piece of Mersenne prime history. You can get a Mersenne prime named after you OR a loved one. The Mersenne prime along with its name, chosen by you, will be recorded in book form in the U.S. Copyright Office. Give a gift that REALLY counts this holiday season. Send your money in an envelope to

Prime Offer
97 Euclid Way
Abuja, Nigera.

Cash only, please. No refunds. Offer not valid in all countries. Employees of the FBI or CIA may not participate. Please.

Re:10 million?

[Ankur Dave]

It wasn't really thousands of dollars. From mersenne.org: "On February 18, 2005, Dr. Martin Nowak from Germany, found the new largest known prime number, 225,964,951-1. The prime number has 7,816,230 digits! It took more than 50 days of calculations on Dr. Nowak's 2.4 GHz Pentium 4 computer."
Wow. 2.4 GHz.

Re:10 million?

[Ben Jackson]

Therefore, by induction, this comment number is also prime!

Re:10 million?

[BarryNorton]

Sorry, but it's a multiple of 3

I can't access the site

[ReformedExCon]

I am curious. Is this the next sequential prime after the previous one? Is it possible that there are other primes between this new one and the one found before it?

Re:I can't access the site

[BarryNorton]

It's definitely possible, and what's more they wouldn't know - they're only going for the easy pickings of Mersenne primes

Re:I can't access the site

[Moby Cock]

It is possible, and in fact, likely. Although they will not be Mersenne Primes. A Mersenne Prime is of the form 2^n - 1, not all prime numbers follow that form (e.g. 11)

Re:I can't access the site

[ReformedExCon]

Makes sense. That's what I was wondering.

Re:I can't access the site

[Anonymous Coward]

There are undoubtedly more primes between this Mersenne prime and the last one as there is roughly a million orders of magnitude between this new number and the previous record. Good luck trying to prove that one of them is prime however. Mersenne numbers are "easy" to prove composite or prime by running the Lucas-Lehmer test. http://primes.utm.edu/mersenne/index.html has some background info.

Re:I can't access the site

[Anonymous Coward]

There are almost certainly a very large number. Mersenne primes are extremely rare compared to ordinary primes.

The Prime Number Theorem tells us that in a region of d around a large number n, there are approximately d/ln n primes. For a 9 million digit n, ln n is about 21 million, so one expects to see one prime every 21 million numbers. For example, between 10^9000000 and 1.1*10^9000000, one expects 5*10^8999991 prime numbers.

Re:I can't access the site

[gnasher719]

'' I am curious. Is this the next sequential prime after the previous one? Is it possible that there are other primes between this new one and the one found before it?''

If p is a prime, then the distance to the next smaller prime is on the average about ln (p). Cases where the gap to the next smaller prime is more than (ln (p))^2 seem to be exceedingly rare. So yes, there are gazillions of primes between this one and the next smaller one.

There may be no Mersenne primes between this one and the previously largest known, because Mersenne primes are indeed very rare.

Re:I can't access the site

[john83]

Can someone tell me exactly what Riemann's hypothesis tells us? Surely you can check with that (assuming it's true ;))?

Re:I can't access the site

[shrykk]

I've been playing with the math myself for primes, but what library or technique do they use to get past 32bits? It's probably simple, but I'd appreciate some help.

You'll probably find this article interesting - it covers prime finding (in C) from naive algorithms to complexe ones involving paging bit arrays in and out of memory: "Fun With Prime Numbers"

Re:I can't access the site

[Mini-Geek]

It's very possible that there are other primes, just not so likely that there are other Mersenne Primes because it would most likely have to be one where the computer printed the wrong result the first time and then the result of the double-check (done by another computer a while later) was found to be different and after more verifications is verified to be prime.
FYI, the verifications are currently running to see if this number is prime before they release the number and the person that found it.

Re:I can't access the site

[hevenor]

Given that n is an integer of course...

How many times I lost marks for forgetting that one!

Re:I can't access the site

[Anonymous Coward]

No. Because of Bertrand's postulate (a.k.a. Chebychev's Theorem) it is known that for every integer n > 1 there is a prime p such that n p 2n.

Re:I can't access the site

[Kjella]

I am curious. Is this the next sequential prime after the previous one? Is it possible that there are other primes between this new one and the one found before it?

It is for all intents and purposes certain. The prime number theorem will give the approximate density of primes, even though it can't locate them exactly so we know there are many many more primes out there. For the rest of the primes we have no efficient way of determining if they are prime. We have very fast algorithms to determine if a number is very probably prime (which is what is used in digital certificates, SSL and such), but not for separating the false positives = pseudoprimes from the real thing. They are rare and of little importance in actual implementation, but these numbers are not mathetically proven to be prime. The Mersenne primes are.

Re:I can't access the site

[p2sam]

yeah, me too. But what kind of a sociopathic marker would think that n could be anything but integers? n can only represent integral values, it's blasphemy to think otherwise!!!

Re:I can't access the site

[slavemowgli]

Unfortunately, what the grandparent wrote is misleading. Yes, the GIMPS project only checks Mersenne primes, so it's entirely possible (highly likely, even) that there are non-Mersenne primes in between them.

BUT it could also be that there's other Mersenne primes in there that we haven't found yet. The exponents the GIMPS project tests are not handed out in sequential order, so there are still "gaps" in there that haven't been checked and double-checked. I'm not sure what the current "watermark" is; the project has definitely checked all Mersenne numbers up to M6972593 (the 38th Mersenne prime), at least, but while finding another Mersenne prime that's smaller than another one already found before is unlikely, it can't be ruled out.

So there just might be smaller Mersenne primes, too (in addition to the smaller non-Mersenne primes that are almost certainly there).

Re:I can't access the site

[amightywind]

I am curious. Is this the next sequential prime after the previous one? Is it possible that there are other primes between this new one and the one found before it?

I am equally curious if this is a twin prime (p + 2 also prime).

Re:I can't access the site

[IDontAgreeWithYou]

Try the NTL(Number Theory Library). I used it in college to write an RSA encryption program.

Re:I can't access the site

[Anonymous Coward]

> Jesus saved me from my past. He can save you as well.

Lectures on religion don't suddenly become any less tedious when presented by people stupid enough to get caught by the police. Please fuck off.

Re:I can't access the site

[Anonymous Coward]

It is possible, and in fact, likely. Although they will not be Mersenne Primes. A Mersenne Prime is of the form 2^n - 1, not all prime numbers follow that form (e.g. 11)

If by "although they will not be Mersenne Primes" you mean that there will not be a single Mersenne prime among then, then you are probably right but not necessarily. As a distributed computing project, GIMPS does not search the Mersenne numbers solely in consecutive order; there could be a yet-to-be-discovered Mersenne prime below this new find.

Re:I can't access the site

[Muhammar]

from what I heard, the new GIMPS-found number is likely M30402457. We should see soon enuff.

Mersenne Primes

[BarryNorton]

Bah, show me a new non-Mersenne prime and I'll be impressed...

Re:Mersenne Primes

[fatphil]

Your wish is my command.

Let Phi(n,x) be the n-th cyclotomic polynomial evaluated at x.
Therefore Mersenne primes are Phi(p,2) for some p.
I found the prime Phi(98304,1063662)=1063662^32768-1063662^16384+1 the other day. However, it is _tiny_ with only 197000 digits (something like the 240th largest in the world).

Lots of people are finding large prime numbers - if you find one over ~64000 digits, it'll be one of the largest 5000 known primes.
See http://primepages.org/

Re:Mersenne Primes

[BarryNorton]

Fair play, I meant "new largest non-Mersenne prime" - i.e. larger than SB8

Re:Mersenne Primes

[MetallicPlastic]

Seventeen or Bust!

Re:Mersenne Primes

[fatphil]

Currently, I expect SoB to be the only project to better their record.

If normalised score is a good measure of a project's size, and capability for finding huge primes, which I believe it is for most projects (which is why I invented the concept in the first place), then the reasons for this expectation become clear:

<URL:http://primes.utm.edu/bios/top20.php?type=pro ject&by=ScoreNormal>
<<<
6517719 Great Internet Mersenne Prime Search
199552 Seventeen or Bust
14285 Yves Gallot's GFN Search Project
5195 Riesel Sieve Project
3390 Prime Internet Eisenstein Search
2031 12121 Search
1219 15k*2^n-1 search
1182 The Prime Sierpinski Problem ...
>>>

As the score for a prime with n digits is proportional to n^3.log(n), we can see that Yves' GFN project, even if it were up to full speed, which it isn't, is 13th the size of SoB. Thus it's only sensibly cabable of finding primes of about 42% of the size at a similar rate to SoB. The rest of us, basically, are nobodies!

Of course, SoB have set themselves a very tricky target. However, that trickiness is one of the things that causes their family of primes to grow in size quite dramatically, if they can keep the CPU input high. It could easily be that they only find two or three more primes due to this incredible growth - the larger ones will just be out of reach to current types of technology. I hope not though.

First Prime Number post

[Anonymous Coward]

2 ~ 25964951-1

keep looking

Why prime numbers ?

[Alarash]

I'm just wondering, what's the point to calculate the largest possible prime number? I mean, there are a lot of distributed computing projects that sound more... useful : Climate Prediction (Hello Katrina), research protein-related diseases or another doing wider research on human diseases. That's just to name a few projects using the Berkeley Open Infrastructure for Networks.

So I'm not being sarcastic here, my genuine questions is : why should I spend my free computing power on calculating prime numbers instead of research to cure cancer?

Re:Why prime numbers ?

[Down8]

As the item suggests: to get a $100,000. :^)

-bZj

Re:Why prime numbers ?

[Anonymous Coward]

One (of many) uses is, IIRC, for public-key encryption.

I don't see how you can feel justified in placing your own value judgement on the utility of such a project, relative to those referenced, whilst critizing that of those participating.

Re:Why prime numbers ?

[Moby Cock]

To be honest. Why not? Sure a cure for cancer would be great, but for some, research for the sake of research is interesting. I am curious as to what Mersenne primes are calculable. Is that not sufficient justification?

Re:Why prime numbers ?

[meringuoid]

So I'm not being sarcastic here, my genuine questions is : why should I spend my free computing power on calculating prime numbers instead of research to cure cancer?

Because you like numbers and think big primes are cool.

Seriously.

This is pure mathematics, it's number theory. Don't expect practical applications; if they turn up, they're a nice bonus, but they're not why you do mathematics.

There may actually be a practical result of this research eventually; the number theory surrounding primes is closely related to the security of the RSA cipher that most of the internet's commerce relies on. It's conceivable that this kind of work might eventually lead to a breakthrough in cryptanalysis. But I wouldn't count on it.

Re:Why prime numbers ?

[gowen]

One (of many) uses is, IIRC, for public-key encryption.

That's a use of prime numbers, and primality, but it's not going to provide a use for this new prime. In the grand scheme of things, this was a pointless exercise. But that's not a bad thing necessarily, as a lot of my favourite things (splatter movies, social cricket, snooker, pub quizzes, bad SF novels) are also pointless exercises, in the grand scheme of things.

Re:Why prime numbers ?

[Alarash]

There may actually be a practical result of this research eventually; the number theory surrounding primes is closely related to the security of the RSA cipher that most of the internet's commerce relies on. It's conceivable that this kind of work might eventually lead to a breakthrough in cryptanalysis. But I wouldn't count on it.

Thanks, that's all I wanted to know.

Re:Why prime numbers ?

[Analogy Man]

I am all for 33,000,000 bit encryption. That ought to keep the NSA's brute force decryption of my subversive activities spinning for a few millenia.

Re:Why prime numbers ?

[Burb]

Because pure mathematics sometimes turns out to have unexpected real-world benefits. Ancient Greek mathematicians such as Apollonius of Perga studied properties of the conic sections (circles, ellipses, the parabola, the hyperbola) as pure maths with no expectation of practical gain. Two thousand years later, we found that planets move in ellipses, that projectiles follow parabolic paths, and so on. Hey presto, that ancient pure mathematics becomes useful...

Re:Why prime numbers ?

[jellomizer]

Unless they start with the big prime numbers first.

Re:Why prime numbers ?

[hackstraw]

This is pure mathematics, it's number theory. Don't expect practical applications; if they turn up, they're a nice bonus, but they're not why you do mathematics.

But someday, we will be able to factor them!

Re:Why prime numbers ?

[Anonymous Coward]

Because the aliens will contact us by sending interlaced hitler video and transport schematics using prime number pulses! you wouldnt want to miss it because you dont know your primes, would you?

Re:Why prime numbers ?

[DenDave]

Actually it works the other way round.. the more primes are known, the less secure your encryption becomes. Brute forcing nowadays is more like a dictionary attack with combinations of primes.

Re:Why prime numbers ?

[Slick_Snake]

What's the point of a large mersenne prime? It is useless. Mersenne primes are easy to calculate and completely pointless for encrytion. Find me a real use for such a number and then I'll care until then I say SO WHAT.

Re:Why prime numbers ?

[gnuLNX]

Depends. Are you using grants from tax payer money for this interesting research or are you self funding it?

Not all research is worht funding just for the sake of pure research....most probably is tho.

Re:Why prime numbers ?

[Darth_Burrito]

Better question... why is the EFF offering prize money for finding primes? It seems only very loosely related to their purpose. That's not the kind of thing I gave them money to do.

Re:Why prime numbers ?

[Viper Daimao]

Yeah, thats exactly what I was wondering. If theres $100,000 dollars being offered for a prime over 10 million digits, then I would think it must have a practicle application. I guess I was expecting more than just, theres a small chance it could help with cryptography. Oh well, I have never given any money to the EFF, so I guess I can't get too bothered by what they do with their money.

Re:Why prime numbers ?

[fatphil]

Brute forcing is not the simplest technique to attack the Number-Theoretic based Public Key algorithms, and never will be.

Therefore negligible changes to brute force techniques produce less than negligible (that's zero) change to how one attacks such algorithms.

Re:Why prime numbers ?

[muhgcee]

From the EFF link: (Prize money comes from a special donation provided by an individual EFF supporter, earmarked specifically for this project. Prize money does NOT come from EFF membership dues, corporate or foundation grants, or other general EFF funds.)

One might think if you were so hot and bothered by this, you'd have clicked on the link to find out more.

Re:Why prime numbers ?

[Anonymous Coward]

In the same vein, why not downgrade your computer to an older model and donate the more powerful one to a cancer charity shop, since you have free computing power and therefore (a) get a computer that fits your needs exactly and (b) feel good about a donation?

The answer is you cant predict what (a) is going to be, and it's the same with pure blue-sky research like prime number calculation.

Re:Why prime numbers ?

[Anonymous Coward]

"So I'm not being sarcastic here, my genuine questions is : why should I spend my free computing power on calculating prime numbers instead of research to cure cancer?"

Because not every single person can, wants to, or should be spending all their spare time/effort/money on a cure for cancer; a cure would be nice, but is everyone looking for really going to find the answer that much faster? People are still working on the problem! As soon as they find something, they'll let us know! In the meantime, there are plenty of other things that need to be figured out.

I'm always tired of the "well, this research is nice but I'd rather they searched for a cure for cancer instead".

Re:Why prime numbers ?

[meringuoid]

Excuse me, but this project it totally useless!

Of course. It's pure maths, done for its own sake. You think these people care for the practical usefulness of their work?

I have never done anything "useful". No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world. I have helped train mathematicians, but mathematicians of the same kind as myself, and their work has been, so far at any rate as I have helped them to it, as useless as my own.

-- G. H. Hardy, A Mathematician's Apology

Re:Why prime numbers ?

[fatphil]

I cannot speak for the EFF. But I do know several people directly involved with the administration of those awards, and have discussed many topics with them.

The smaller prizes - 1M digit (already awarded), and 10M digits (still pending) are actually pretty small and unimportant. They can be attacked simply by throwing huge numbers of inexpensive commodity PCs at the task. That's basically what GIMPS is. The larger prizes are the important ones, as they reward a much harder achievement. The algorithms used to tackle such tasks don't scale particularly well. It's more than 10 times harder to do a problem 10 times bigger. This in part is because of the hierarchical memory system that PCs have. Small fast caches, other medium-sized slower caches, and then large quantities of relatively slow main memory. FFTs really don't like such a hierarchical memory architecture, as they grab data from all over the place all of the time. Caches become very hard to use effectively, and enormous L1 caches are prohibitively expensive.

So these later prizes will almost certainly be awarded to systems either based on new algorithms that are vastly more scalable than current FFTs, or on new hardware (memory) designs which somehow get around the caching issue.

Moving up to even larger sizes, it may become impractical to perform such calculations on a single PC. Therefore communications systems will want to be invented that provide no more latency than main memory.

Those are real concrete advances in computer technology, and it's those that are being rewarded. The primes are almost a red herring.

Re:Why prime numbers ?

[Mantorp]

Then the question is why do these people care enough about it to donate money for this cause specifically rather than curing cancer or finding aliens? It's the old, why do people care about saving old buildings or seemingly insignificant insects when there are people starving? Or to put it in ./ context trying to resurrect sci fi shows that were taken off the air instead of whatever...

Re:Why prime numbers ?

[texaport]

This is pure mathematics, it's number theory.

Nah, it's applied science. Fire up an instance of Prime95 on a low-end Dell or HP unit,
heat them up for a few hours and see what is left over (sorry small form factor machines)

Survival of the fittest ...

Re:Why prime numbers ?

[fastgood]

the more primes are known, the less secure your encryption becomes

But the more we know about those people who calculate primes in their spare time,
the safer America will become.

Re:Why prime numbers ?

[Anonymous Coward]

The more americans calculate primes in their spare time the safer the world will become...

Re:Why prime numbers ?

[imsabbel]

Sorry, this project is NOT maths.
Developing the algorithms was maths. Running them on 1000s of computers wasting resources is just like trying to to verify that 2*a = a+a by calculating it for all a`s.... A waste of time and no benefit for science or math.

Re:Why prime numbers ?

[pomakis]

why should I spend my free computing power on calculating prime numbers

So you can determine the optimum number of buckets for a really really really really large hash table?

Re:Why prime numbers ?

[slavemowgli]

Excuse me, but this project it totally useless!

Well, yes. Just like music, movies, books, computer games, nice food, non-reproductive sex, voyages, and everything else that's enjoyable in life.

Since when has "useful" become a requirement for activities that people are allowed to enjoy?

Re:Why prime numbers ?

[Darius Jedburgh]

why should I spend my free computing power on calculating prime numbers instead of research to cure cancer? Because, despite the claims of many researchers, you can't actually cure cancer using computing power.

I'm saying this as someone who once worked in computational chemistry and quickly figured out that the whole department was an Emperor's New Clothes type of project. It's very difficult to find proper validation of in silico work. Someone might screen millions of compounds digitally and come up with a shortlist and find that a high proportion of compounds on that list bind to some receptor, or block such binding, without pointing out that (1) a similar proportion from a random selection of compounds might do just as well or (2) that the correlation between receptor binding and effectiveness as a drug can be incredibly small. I was pretty disgusted with the whole business.

Re:Why prime numbers ?

[Anonymous Coward]

Right.... well I can prove 2 * a = a + a, based on fundamental axioms and that is math. This project is 'maths' because it seeks to discover something new about the mathematical world we live in. Why is there a money reward for a 10 million digit prime? Because industry and cryptographers want more/bigger primes in order to increase the complication of their cyphers. If some how, you could discover some new formula, like you example 2*a=a+a that proves or disproves whether a number is prime, this would be maths, also anything that may help in the discovery of such a formula or method, like the actual values of primes for such high order numbers is also maths for statistical uses or whatever is also math.

Further, evaluating 2*a=a+a for all a, *would* provide a benefit to science, because science relies on the accumulation of evidence and knowledge through exploration and documentation of experience. Like looking closer through a microscope or testing a material for strength. This calculation has never been done before, if it could, it might help satisfy the implicit doubt all those who understand the scientific method will have (how do you prove, or validate an axiom?), and in turn increase existing evidence and further the knowledge and understanding of all humanity.

Re:Why prime numbers ?

[muhgcee]

All questions are such that we (well, at least me) are unlikely to be able to coherently answer them without further research into the benefits of each one of these causes.

Re:Why prime numbers ?

[glenrm]

Don't you see finding the biggest prime number = protecting your rights online!

Re:Why prime numbers ?

[kadathseeker]

Don't expect practical applications; if they turn up, they're a nice bonus, but they're not why you do mathematics.

That's exactly what I told my math teachers, and they never listend!

Re:Why prime numbers ?

[VAXcat]

Yah...when primes are outlawed, only outlaws will calculate primes.

Re:Why prime numbers ?

[deangelo]

Actually there is anther pratical application, it keeps tabs on computing power as it relates to factorization, this does have some significant security implications.
        deangelo

Re:Why prime numbers ?

[Darth_Burrito]

ah that makes sense then. The publicity they get from this might even help them raise additional funds which can be applied to their primary goals. I wasn't really bothered so much as confused.

Re:Why prime numbers ?

[hmccabe]

How does knowing prime numbers help anyone figure out that my password is k1n6c4tf15h?

Re:Why prime numbers ?

[karthikg]

Mersenne prime finding is not the same as verifying a universal truth like 2*a = a+a. It is *NOT* yet proven that the number of Mersenne primes is infinite. So it is not a guarantee that you run a huge collection of machines and you always find the next bigger mersenne prime. The fact that we do indeed find them, makes it more convincing that the conjecture (that the number of mersenne primes is in fact infinite) is true.

Re:Why prime numbers ?

[DenDave]

Well perhaps: http://en.wikipedia.org/wiki/RSA may give you an idea..

Re:Why prime numbers ?

[imsabbel]

Well, the point is: Finding a bigger one does ZERO for math.
A conjecture doesnt become more convincing because you know 5 more numbers. Math doesnt work that way (surely you know the old joke how an engineer finds prime numbers: "1 check. 3 check. 5 check 7 check-> its convincing odd numbers are prime" Some way of thinking)

BTW, this is cute

[ReformedExCon]

The ID for this story is 171673 which is itself a prime number.

Clever clever!

Re:BTW, this is cute

[chillmost]

Nerd!

Re:BTW, this is cute

[njchick]

The ID for this story is 171673 which is itself a prime number.

Extra credit to /. editors if the dupe story ID will also be a prime.

Re:BTW, this is cute

[Bastard of Subhumani]

Unlikely, you don't often get two consecutive numbers that are prime.

Re:/.ed - Care Factor?

[Anonymous Coward]

Care factor = 0

FB!!!

FYI

[Walterk]

The next largest known prime, as of today, is 225964951 1 (this number is 7,816,230 digits long); it is the 42nd known Mersenne prime. M25964951 was found on February 18, 2005 by Martin Nowak, a member of a collaborative effort known as GIMPS.

The third largest known prime is 224036583 1 (this number is 7,235,733 digits long); it is the 41st known Mersenne prime. M24036583 was found on May 15, 2004 by Josh Findley (member of GIMPS) and it was announced in late May 2004.

The fourth largest known prime is 220996011 1 (this number is 6,320,430 digits long); it is the 40th known Mersenne prime. M20996011 was found on November 17, 2003 by Michael Shafer (and GIMPS) and announced in early December 2003.

Historically, the largest known prime has almost always been a Mersenne prime since the dawn of electronic computers, because there exists a particularly fast primality test for numbers of this form, the Lucas-Lehmer test for Mersenne primes.

The largest known prime that is not a Mersenne prime is 27653 × 29167433 + 1 (2,759,677 digits). This is also the fifth largest known prime of any form. It was found by the Seventeen or Bust project and it brings them one step closer to solving the Sierpinski problem.

Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256k for some positive integer k, and searching for possible primes within the interval [256kn + 1, 256k(n + 1) 1].

Re:FYI

[gowen]

The largest known prime that is not a Mersenne prime is 27653 × 29167433 + 1.

Erm... isn't that an even number?

(Yes, I know, your "to the power of" got nobbled).

Re:FYI

[Anonymous Coward]

This is just a copy/paste from the Wikipedia entry on prime numbers. For crying out loud, mods!

Why anything?

[Poromenos1]

Why do people calculate digits of pi? Why do they scale mt. Everest? Because they have small penises.

Re:Why anything?

[dchallender]

What about the women?

Re:Why anything?

[richie2000]

"No penis" is just a special case of "small penis".

Re:Why anything?

[fatphil]

Sophie Germain was a female who made important advances in number theory, inparticular to do with prime numbers (and Fermat's Last Theorem).

When this prime:
http://primes.utm.edu/primes/page.php?id=20278 885817959*2^24712-1
was found, several years ago, it was something like the 7th largest known Sophie Germain prime in the world. The finder, like Sophie, was female. Both were and are utterly devoid of (their own) penis.

Alas it's no longer one of the top-20 Sophie Germains, but time marches on at a frightening rate, and primes are growing at an amazing rate:
http://primes.utm.edu/top20/sizes.php

Re:Why anything?

[Anonymous Coward]

She must have small tits, then..

Re:Why anything?

[jbridge21]

Nah, people climb mountains cause they look like breasts :)

Useless numbers

[Anonymous Coward]

Yes and add to that useless numbers too. They can't now be used in cryptohraphy because they are now 'known'.

Also, who cares? It's not like there is a finite supply of prime numbers.

I'm aiming at the $150,000 prize

[CortoMaltese]

I'm aiming straight at the EFF prize of $150,000 for discovering a prime number with at least 100,000,000 decimal digits.

You can join the effort!

Re:I'm aiming at the $150,000 prize

[moonbender]

Most important note to this story: (Prize money comes from a special donation provided by an individual EFF supporter, earmarked specifically for this project. Prize money does NOT come from EFF membership dues, corporate or foundation grants, or other general EFF funds.)

So at least they're not wasting your membership fees on this "huge scientific problem".

Headlines

[sanctimonius hypocrt]

The number of primes found lately, four in just over two years, is higher than previously expected.

I can just imagine the newspaper report: Scientists report more numbers than previously thought.

Re:Headlines

[HD Webdev]

I can just imagine the newspaper report: Scientists report more numbers than previously thought.

That's an Onion worthy headline!

Re:Headlines

[Hognoxious]

"Scientists report more numbers than previously thought."

Easily explained - dark numbers.

MOD PARENT UP

[Anonymous Coward]

Call me a petty man, but I love to see egg on the face of karma whores...

FPGA prime number calculator

[cheesy9999]

I made a FPGA based prime number calculator back in one of my EE courses and it was pretty freakin fast. They should make a giant super optimized version of my little thing.

Re:FPGA prime number calculator

[cheesy9999]

i found all my old project files if anyone cares...unfortunately it only works up to 8 bit numbers :-\

Re:FPGA prime number calculator

[marcantonio]

Hehe, that's what she said!

Re:FPGA prime number calculator

[Ken_g6]

There once was a dedicated prime-finding device called a Dubner Cruncher, but those are getting pretty old.

Biggest useless (yet meaningful) number ever?

[Sockatume]

Is there another candiate?

Re:Biggest useless (yet meaningful) number ever?

[shreevatsa]

Yep. I remember reading a Number Theory book long ago that Skewe's number 10^10^10^34 was "the largest number which has ever served any definite purpose in mathematics", but apparently, things have changed since then. The largest meaningful (but useless, as you pointed out) number used is apparently Graham's Number, which has even been listed by the Guinness Book of World Records as such. Tetration is explained here, or quite a lot of notation is explained here.

The best page about large numbers, however, is clearly the one at MROB, beautifully written.

But the amusing thing about this Graham's Number is that it is an upper bound on some quantity, which experts believe is equal to 6. That's right, SIX. So it's not only the largest number ever used; it's also probably the worst upper-bound ever :)

Re:Biggest useless (yet meaningful) number ever?

[Sockatume]

You know, I'd read about that one (in something about the Reimann hypothesis, I think) and forgotten about it. The new upper bound is one heck of a punchline.

Re:Biggest useless (yet meaningful) number ever?

[Hado]

Actually, the lower bound has been proven to be at least 11. From the link:

Graham and Rothschild (1971) also provided a lower limit by showing that N* must be at least 6. More recently, Exoo (2003) has shown that N* must be at least 11 and provides experimental evidence suggesting that it is actually even larger.

Still, it's quite a range.

Re:Biggest useless (yet meaningful) number ever?

[slavemowgli]

But the amusing thing about this Graham's Number is that it is an upper bound on some quantity, which experts believe is equal to 6. That's right, SIX. So it's not only the largest number ever used; it's also probably the worst upper-bound ever :)

Actually, the lower bound has recently (a few years ago) been improved to 11.

And FWIW, Graham's number is not the largest number ever used, either, not by far. It's the biggest *natural* number ever used, but generally, numbers only get really big when you have to talk about them in terms of consistency strength. ;)

Probably?

[digitaldc]

Why only probably? Just divide it by 2 and see if it comes out even.

I tried reading the page, but I got:

Network Error (tcp_error)

A communication error occurred: "Connection refused due to prime number calculation"
The Web Server may be down from exhaustion, too busy calculating a very long prime number, or
experiencing other problems preventing it from responding to requests. You may wish to try again at a later time.

For assistance, contact your prime number support team.

Re:Probably?

[BarryNorton]

Why only probably? Just divide it by 2 and see if it comes out even.

I think you're confusing odd and prime numbers...

Re:Probably?

[Anonymous Coward]

I hope you're kidding.

(If you're not, consider 9, not prime. And, not divisible by 2)

Re:Probably?

[shreevatsa]

Or he has taken this proof of All odd numbers are prime very seriously ;)

My favourites from that list:

Physicist:
3 is prime, 5 is prime, 7 is prime, 9 is an experimental error...

Logician:
Hypothesis: All odd numbers are prime
Proof:
1. If a proof exists, then the hypothesis must be true
2. The proof exists; you're reading it now.
From 1 and 2 follows that all odd numbers are prime

and oh, lots of others.

Another one of note:

GNU programmer:
% prime
usage: prime [-nV] [--quiet] [--silent] [--version] [-e script] --catenate --concatenate | c --create | d --diff --compare | r --append | t --list | u --update | x -extract --get [ --atime-preserve ] [ -b, --block-size N ] [ -B, --read-full-blocks ] [ -C, --directory DIR ] [--checkpoint ] [ -f, --file [HOSTNAME:]F ] [ --force-local ] [ -F, --info-script F --new-volume-script F ] [-G, --incremental ] [ -g, --listed-incremental F ] [ -h, --dereference ] [ -i, --ignore-zeros ] [ --ignore-failed-read ] [ -k, --keep-old-files ] [ -K, --starting-file F ] [ -l, --one-file-system ] [ -L, --tape-length N ] [ -m, --modification-time ] [ -M, --multi-volume ] [ -N, --after-date DATE, --newer DATE ] [ -o, --old-archive, --portability ] [ -O, --to-stdout ] [ -p, --same-permissions, --preserve-permissions ] [ -P, --absolute-paths ] [ --preserve ] [ -R, --record-number ] [ [-f script-file] [--expression=script] [--file=script-file] [file...]
prime: you must specify exactly one of the r, c, t, x, or d options
For more information, type "prime --help''

Re:Probably?

[digitaldc]

Kidding indeed....good luck on the number crunching earthlings, I am going to use my distributed computing power to look for ET.

http://setiathome.ssl.berkeley.edu/

Re:Probably?

[FirienFirien]

"Just divide it by 2"

What on earth are you talking about? At first look, you seem to be thinking of "odd numbers", a fascinating concept made yet simpler by the fact you don't even have to divide the huge number by anything, just look at the last digit and see whether it's odd or even. Yet that still doesn't fit with your 'divide it by 2 and see if it comes out even; you seem to take "prime number" to mean "anything that isn't divisible by 4".

Re:Probably?

[geoffspear]

I'm still waiting for someone to publish the largest known odd number. I plan to memorize it to impress women.

Re:Probably?

[psergiu]

Here it is. Just spell-it out to them digit by digit and they will be all over you when you finish.

For newbies

[chord.wav]

If you think this is your grand chance to win money easily using GIMPS, think again.

As it states here

If you were to find a 10,000,000 digit prime today the above rules imply that $5,000 would go to Michael Cameron, discoverer of the 39th known Mersenne prime, $5,000 would go to Michael Shafer, discoverer of the 40th known Mersenne prime, $5,000 would go to Josh Findley, discoverer of the 41st known Mersenne prime, $5,000 would go to Dr. Martin Nowak, discoverer of the 42nd known Mersenne prime, $0 would go to discoverers of algorithmic breakthroughs, $5,000 would go to GIMPS primarily to fund future awards, $25,000 would go to charity, and $50,000 would go to you.

Now the bad news. Testing a single 10,000,000 digit number takes two months on a 2 GHz Pentium 4 computer. Your chance of success is roughly 1 in 250,000.
Someone may find a 10,000,000 digit prime before GIMPS does.

Re:For newbies

[BarryNorton]

Your chance of success is roughly 1 in 250,000

Better than buying a lottery ticket?!

Re:For newbies

[Anonymous Coward]

1 in 250000? That's a whole lot better than the odds in a typical, large jackpot lottery. In fact, it is roughly on par with getting struck by lightning if you live in the US (and, odds of dying in a given year, not merely being struck, are worse than 1 in 4 million). So, 1 in 250000 is pretty good, because the odds for winning lotteries are usually worse than the odds of being struck by lightning.

Re:For newbies

[woolio]

That's still better odds than the state lottery!

And it can be a good way to help your computer serve as an effective space-heater during these winter months... Quite a good deal in all.

Upon further review...

[dynayellow]

It was revealed that the new number ends in a 2.

Re:Upon further review...

[iphayd]

Eureka!

I needed a prime number ending in two (that is not two) for my Cold Fusion generator and Perpetual Machine.

It also will allow me to make Windows virusproof.

Re:Upon further review...

[Anonymous Coward]

Due to a fencepost error in the code, the answer was off by one.

why go for under 10k?

[v1]

If I'm reading this correctly, the reward for a prime > 10k digits is twice that the reward for the next prime 10k. So wouldn't it make more sense for them to skip ahead to 10k digits and start looking there instead?

Re:why go for under 10k?

[Markus Landgren]

It's 10M, not 10k. And the EFF award for another prime below 10M digits is zero, no more payouts will occur until someone finds a number with at least 10M digits. But GIMPS was around long before the EFF award was announced. They are systematically testing "all" mersenne numbers, not only those elegible for prizes. Ultimately, it's up to the participants. The client has a checkbox for only downloading assignments big enough to qualify for the prize.

Re:why go for under 10k?

[Anonymous Coward]

Huh?

You are reading it wrong. That k is a prefix, and as you probably did not understand, it is used to make a unit 1000 times bigger. One kJ is 1000 Joule, not a million.

There is a prize for 10 million digits and one for 100 million digits and one for a billion (or milliard) digits. Skipping one of the rewards for 50 percent more reward does not look very smart to me, since you have to find a prime number that is about 10^90,000,000 times bigger.

If you try to argue that finding a prime number with less than 10,000,000 digits is useless because you dont get the EFF prize, then you should realize that it is not only about the reward.

Radical compression scheme

[benhocking]

Consider this as a radical compression scheme. Rather than storing every single digit, you store a simple formula for arriving at the number. In this case, that formula is 2^x-1. All you need to store is x, which requires O(lg n) bytes to store where n is the number of digits in the original number.

What strikes me as somewhat amusing is that calculating 2^x-1, for an arbitrarily large x, requires O(2^x) amount of time. Of course, since 2^x is less than 10 million here, and it's actually quite a small bit of work O(2^x) times, it's no big deal.

Re:Radical compression scheme

[pjt33]

What do you mean by "calculating"? Converting to base 10? You can convert to base 16 in O(x) time.

Re:Radical compression scheme

[Anonymous Coward]

What strikes me as somewhat amusing is that calculating 2^x-1, for an arbitrarily large x, requires O(2^x) amount of time.

No, it doesn't.

It requires O(x) amount of time.

Re:Radical compression scheme

[Hawkxor]

I'm pretty sure this is done with O(log x) multiplications by first squaring 2 and then squaring the result, etc.. to fill in 2^x

Re:Radical compression scheme

[ganhawk]

"Consider this as a radical compression scheme. Rather than storing every single digit, you store a simple formula for arriving at the number."

This is one of the principles of algorithmic information theory. But the poster above has also elaborated on a similar scheme as we just need to store the number of digits.

Re:Radical compression scheme

[Anonymous Coward]

exact, and also 2^x is not less than 10 million, it's just under 10^(10 million) !

Re:Radical compression scheme

[Anonymous Coward]

Indeed. I was just finding that amusing myself.

So clever of you to pick up on the irony!

Re:Radical compression scheme

[iamlucky13]

That's all well and good, but the original poster's point was more about the slashdot hordes who are unable to see the number like they want (in decimal notation). Sure you can send it to the use along with a javascript file to display it in their browser with just a few kilobytes, but when the javascript executes, woe to the browser!

Better tell me...

[Vo0k]

how much do I get for finding the extraterrestial in SETI@Home?

Re:Better tell me...

[Alibloke]

1 free anal probing!

Re:Better tell me...

[RonStoppable102]

It's not a cash prize, but I think it involves a probe...

Re:Better tell me...

[mbelly]

They likely won't tell you if you found something on SETI.

Re:Better tell me...

[Anonymous Coward]

You get to be the first person to say
"I for one welcome our new ...." in earnest.

First Prime Factorization Post?

[InsaneLampshade]

Where's that guy when you need him most? :(

Re:First Prime Factorization Post?

[Gobelet]

Exactly my thoughts.

Ob southpark

[Anonymous Coward]

President Hirohito: You are American who calculate PI?
Red: Yes.
President Hirohito: [begins to gesture] Ogh! You must have very big pee-anis!
Red: Excuse me? I was just asking you what you're up to with this real world use of computers!
President Hirohito: Nothing. We are very simple people. With very small penis. Mr. Ose penis is ...especially small.
Mr. Ose: [fakes a sob] Uh, smuh, so small.
President Hirohito: We cannot achieve much with so small penis. But you! Americans who calculate PI. Wow! Penis so big! SOOO big penis!
Red: [flattered] Well uh, he-I guess it is a pretty good size.
Mr. Ose: Minata, kite kite! ["Everone, come come!" A group of Japanese women move in, chattering] This-a man has veh-ry big penis! [the women applaud, Red grins big]
Woman 1: Take takeru o da ne? ["It's rather large, isn't it?"]
Woman 2: Hai. ["Yes."]
Mr. Ose: Uh, hoh, what an-whoa immense penis-uh!
Red: Well, it certainly was nice meeting you folk, I just wanted to bring that little waste of resources to your attention. Bye-bye now.
President Hirohito: Good-bye. Thank you for stopping by, with your gargantuan penis.

Prime numbers aren't all that rare.

[DocSavage64109]

If you just wanted a ten million digit prime number, just make one... I'll bet 100000...(10 million 0s)...13 would be prime and if it isn't, just change the end from 13 to 17 or some other likely candidate.

Re:Prime numbers aren't all that rare.

[Smuffe]

Actually, 10 000 000... 17 is not prime since it's divisible by 9 (and 3).

No word yet on the 10 000... 13 one

Re:Prime numbers aren't all that rare.

[Anonymous Coward]

The trouble isn't making an arbitrary number in the hopes that it's prime, it's in proving that it's prime. There are relatively simple methods to look for Mersenne primes, they just take constant time for crunch. For non-Mersenne primes, you'd have to crunch out every possible factor to prove that it's prime, a tedious process. The goal isn't to discover every prime number, there are far too many. We just want bigger prime numbers because it's a challenge. If you want to make arbitrary primes, you're free to, just know that it'll be a pain to prove it is prime.

Oh, and FYI, 1 000 000 ... 017 was debunked rather easily due to the fact that in base 10, if the sum of the digits is divisible by three (1+1+7=9, 9%3=0), then the number itself is divisible by three as well. It's covered at Wikipedia and the other repository of all geek knowledge, bash.org. Proving something's not prime can be surprisingly easy.

Re:Prime numbers aren't all that rare.

[Jerry Coffin]

The trouble isn't making an arbitrary number in the hopes that it's prime, it's in proving that it's prime. There are relatively simple methods to look for Mersenne primes, they just take constant time for crunch. For non-Mersenne primes, you'd have to crunch out every possible factor to prove that it's prime, a tedious process.

This is not even close to correct. Testing primality this way becomes impractical around 30-40 digits or so (depending a bit on how patient you are) and there are methods that are faster even with substantially smaller numbers than that.

First of all, there are probabalistic methods of testing primality that don't involve factoring. While probabalistic, these can be carried to an arbitrary level of accuracy quite quickly and easily. This is a typically done as a preliminary before more difficult methods are attempted at all.

Once you're convinced that a number is almost certain to be prime, there are quite a few methods of proving it's prime that are faster than brute force -- probably the oldest and best known is based on Fermat's Little Theorem. There's also something known as Wilson't theorem that can prove the same thing, but TTBOMK, this rarely has much practical application. If you're interested in more, you can find a fairly reasonable introduction a number of the better-known factoring methods and such here. You can find more links about factoring here.

Re:Prime numbers aren't all that rare.

[Ken_g6]

It's not clear exactly how many 0's your numbers have. But testing around that range, 10^10000000+13 is not divisible by any number less than 8 billion, according to NewPGen. When testing to 1 trillion, I find that around 1/100 numbers tend not to be factored. The Prime Number Theorem says that roughly 1 in 23 million numbers of that size will be prime. So this number has a roughly 4 in a million chance of being prime.

Anybody want to run a PRP test on this number? It will probably take at least 2 CPU-months.

Re:Prime numbers aren't all that rare.

[DocSavage64109]

I found a nifty little website: http://www.alpertron.com.ar/ECM.HTM to try smaller versions of 10^(100,200,etc.)+(3,13,etc.) and I couldn't find any prime numbers. I suppose analyzing patterns in primes up to 1 million (only 6 digits) is not very indicitive of 10 million digit prime number patterns.

Run Prime# lettery and profit now

[La Gris]

Frofit out of it now:

1) Setup server farm
2) Accept prime candidate for minimal fee covering costs + profit
3) If prime is OK, get the prize and give back part of it.
4) Profit

The bad news

[OhHellWithIt]

"Upon visual inspection, the new prime number was found to be a factor of two."

Okay, so I made that up. But how are they going to prove it's a prime? And, more importantly, does it taste good?

Re:The bad news

[hotdiggitydawg]

how are they going to prove it's a prime?

Personally I'd start here. As of 2002 this problem can be solved in polynomial time.

Re:The bad news

[rbarreira]

I would start here instead... Read the part about Lucas-Lehmer testing...

New Possible Record Prime Number Found

[anshil]

Smallest Positive Mersenne Prime-Number ever: 3

Hey, also small is beatuiful.

Re:New Possible Record Prime Number Found

[Anonymous Coward]

2^1-1=1 is a prime too.

Re:New Possible Record Prime Number Found

[the computer guy nex]

2^1-1=1. 1 is by definition prime, mathematicians convieniently forget it to make other math work :P

Re:New Possible Record Prime Number Found

[trilliwig]

No, 1 is by definition a unit, which is a distinct category from primes or composites.

http://primes.utm.edu/notes/faq/one.html

Re:New Possible Record Prime Number Found

[Anonymous Coward]

hehhh heh heh hehhhhh, he said,,,,, *unit*, hehhh hehhhhh

$100k!!

[Anonymous Coward]

It's the time of the year for giving, and EFF does really important things. I'm considering cracking open the checkbook for them, but does the EFF spend its money efficiently? Does it spend every last $100k on lawyers to protect what few digital rights we have left? Or does it instead spend $100k (actually, $500k if you read the link) on prizes for big prime numbers, as if that research wouldn't be done anyway? Well, I guess I know the answer. :-( I can't believe it. $1k? $10k? I can see those symbolic gifts. Five hundred thousand dollars?? Incredible.

Re:$100k!!

[J2000_ca]

it comes from a special fund that is donated only for that. If you donate to the eff it won't be used for primes unless you tell them to.

size matters

[Anonymous Coward]

Mine "prime" is bigger than yours.

100000...(10 million 0s)...17

[PeDRoRist]

can be divided by 9 (or 3).

Finally

[Stan Vassilev]

Finally we got a Mersene number just under 10 million digits! I mean seriosly, with this number in possession just imagine the possibilities. Like... uhmmmm...

uhmmm....

oh never mind.

Products of primes

[ockegheim]

Last week while factorizing random 5 digit numbers with a calculator (very bored at work) I decided that if a number has two prime factors it can't have any other factors. Is this true, and is the mathematics behind it obvious or complicated?

Re:Products of primes

[Anonymous Coward]

Of course it's not true. The simplest counter-example is 30, which has the prime factors 2,3 and 5.

Re:Products of primes

[ockegheim]

Oops, I meant if a number is the product of two primes is there a proof it has no other factors. Sorry, it's too late at night here

Re:Products of primes

[Lord Crc]

[...] if a number has two prime factors it can't have any other factors. Is this true, and is the mathematics behind it obvious or complicated?

A composite (ie non-prime) number is a product of at least two prime numbers, otherwise it would be a prime number. That follows directly from the definition of a prime number. A composite number can have more than two (different) prime factors though. Take your favorite number 42 = 2 * 3 * 7. Or if you want a 5 digit number: 11 * 23 * 127 (a Mersenne prime, btw :) = 32131. Since there's no mathematical law against which numbers you can multiply together, you can use as many prime factors you want to generate a number.

Re:Products of primes

[VMEbus]

This is not true in general since you can easily construct a number n where

n = p1 x p2 x s

where p1, p2 are prime and s is not (and the factors of s are != p1 or p2)

Re:Products of primes

[Anonymous Coward]

OMG yes it's true, because 2x3x5 is not a number; neither is 2x3x7 or any other product of more than two prime factors.

Seriously, what do you think happens if you multiply together more than two prime factors?

Re:Products of primes

[VMEbus]

I think your statement itself is sufficient proof:

if n = p1 x p2, where p1 and p2 are prime, (i.e. have no other factors) then it
follows that n has no other factors.

Re:Products of primes

[WalksOnDirt]

Yes, it's called the Fundamental Theorem of Arithmetic http://mathworld.wolfram.com/FundamentalTheoremofA rithmetic.html

Re:Products of primes

[ockegheim]

Wow, this is an awesome site for those of us who want to know mathematical facts, even if we could never understand the proofs.

I bet that's on a freaky curve

[epaga]

At http://www.numberspiral.com/ somebody figured out that if you spiral numbers around, keeping square numbers next to each other, you get some freaky beautiful curve patterns. I wonder if this new one is on one of those curves.

First Prime Factorization Post

[Anonymous Coward]

1 * 225,964,951-1

Whao this has so many digits

[Arthur B.]

I'm totally using it to produce my GPG secret key, with so many digits it'll never be cracked!!

Re:Whao this has so many digits

[Ken_g6]

Except that people will see that your GPG key is so large it has to be composed of one of a very few primes that have enough digits. That narrows the search to one or two primes.

Not to mention that using a prime of this form means Williams' P+1 method will crack your key in no time!

Re:Whao this has so many digits

[Arthur B.]

I guess the moderators were people like you... I was aiming for +5 funny...

So, will THIS GIMP be...

[davidsyes]

EFF'ed? That's going to be quite some long digita...

Sorry, i just had to...

Wow!

[Chemisor]

I finally have an unbreakable number to use as my GPG key!

How do they check a number that big for primeness

[doctorjay]

Do they recursively calculate if all the numbers before it modulus divide out to zero? Or something along those lines?

WTF?

[UnknowingFool]

The Great Internet Mersenne Prime Search (GIMPS), a distributed computing project, has probably found a new record prime number

Damn it! Now I have to change my luggage combination again. You bastards.

Re:WTF?

[bk4u]

just do what I do, use 1-2-3-4-5

Re:WTF?

[UnknowingFool]

How did you get my root password?

Converting to base 16, base 2, whichever

[benhocking]

If you want to just represent this as 111...111, it will obviously require O(n) or O(2^x) time, since there are O(2^x) digits. To represent it as FFF..FFF (or 3FF..FFF, etc., depending on the situation), will require O(n/16) time which is still O(n) or O(2^x), by definition of O().

Converting to base 10 is also only O(n), but would be slightly slower, of course.

Re:Converting to base 16, base 2, whichever

[pjt33]

No, 2^x-1 has O(x) digits.

What's a prime number?

[Anonymous Coward]

Flame on!!

Shit I lost the number

[Anonymous Coward]

it was lying around here somewhere on a notepad. Damnit!

Subtracting 1 requires O(n) carries

[benhocking]

2^x = 1000...0000 in binary.

2^x-1 = 111...1111.

There are intelligent ways to do this very quickly; however, it's still O(n), or O(2^x), where n is the number of digits. Let's assume that you have an infinite number of 64-bit registers, and each register can subtract one in constant time (for a fixed size register, this is a trivial statement). If you have n binary digits, then you'll require n/64 registers to store 2^x. Two carry the subtraction from each register will require O(n/64) time, and O(n/64) is synonymous with O(n), by definition of O().

The same logic applies if you're dealing with RAM instead of registers.

Also, I should point out that by similar reasoning you can see that assigning the registers (or RAM) to hold 2^x will require O(n) even before the subtraction takes place.

Re:Subtracting 1 requires O(n) carries

[bradkittenbrink]

x == n == the number of digits in 2^x-1, the algorithm is O(x), not O(2^x)

Re:How do they check a number that big for primene

[Jerry Coffin]

Do they recursively calculate if all the numbers before it modulus divide out to zero? Or something along those lines?

No -- for Mersenne numbers, they usually use the special number field sieve.

Darn It!

[Nom du Keyboard]

This prime is just under 10 million digits

To big for my /. .sig, darn it!

Related news: Perfect number

[Big_Oh]

In related news, a new perfect has been found. It has roughly twice as many digits as the most recent Mersenne prime. Like all other known perfect numbers, this one is also even.

Cancer as nature

[SeanDuggan]

I'm always tired of the "well, this research is nice but I'd rather they searched for a cure for cancer instead".
Besides which, cancer is part of life. Any living organism that survives to the late years is going to contract some form or degree of cancer. Really, we brought it upon ourselves by extending the longevity of the human race...

Above text is to read with tongue firmly in cheek. Any offense generated by reading in any other mode is entirely the fault of the user.

Prime sphere looks like the death star

[ApolloCreed]

Is it just me or does that last image look like the deathstar? They both have a ridge that divides them in half, but the ridge on the number spiral only goes halfway across.

Re:How do they check a number that big for primene

[Quantum_Mechanic_196]

No -- for Mersenne numbers, they usually use the special number field sieve.

Um, don't you mean the Lucas-Lehmer test?

Re:How do they check a number that big for primene

[Jerry Coffin]

Um, don't you mean the Lucas-Lehmer test?

Oops -- yes, that would be the right one.

Re:How do they check a number that big for primene

[Anonymous Coward]

Not to be overly harsh on your post, since in truth there are a dozen other posts in this story which are equally wrong, but this post is just plain wrong. The fact that someone modded it (along with those dozen other posts) "Informative" just compounds the damage.

The special number field sieve is an integer factorization algorithm. It is not generally used for primality testing. The task of primality testing is in practice dramatically different from integer factorization, even though to one uneducated or moderately educated in mathematics the two problems might appear similar. In particular, the special number field sieve runs slower than polynomial time, so running it on a number of 10 million digits is wildly impractical.

Primality testing for Mersenne numbers is actually performed using the Lucas-Lehmer test, which runs in polynomial time and has little to do with the special number field sieve or indeed with any integer factorization algorithm at all.

Name suggestion

[Spy der Mann]

Can we call this number the "Optimus Prime"? :)

Whis is prime important?

[boyzscout]

Can anyone tell me why prime numbers are so valuable?

Re:Whis is prime important?

[ClamIAm]

here you go.

Um, yeah

[benhocking]

I was just testing you. You passed! Congratulations!

I like Prime Rib

[Anonymous Coward]

I like Prime Rib.

So it does

[benhocking]

I shamefully retract most of my previous comments on the topic.

Couldn't they

[Anonymous Coward]

spend the money on hungry children in Africa or something?

Even more over...

[voxel]

Moreover, 2759677 has 7 digits, which is prime too! How fun.

Even MORE fun! The number 7 has 1 digit, which is prime too! I think I wet myself.

Article Title

[Joe at Axual]

I have "found" the following "possible" prime number:

45345098123004327872340236020100023240555023412060
54643322939871009128740203470123210210040347280109
28425769812020347291732192731234987y68712304329812
931976432510901237687432o5203012739840590120934920
03701927439750012043259495776871230923748765128370
92438597691826398716235083497501974320917324041234

It may not be prime, but it's possible. Aren't all numbers "possible" prime numbers?

Joe at ewizmo.com

Re:Article Title

[Anonymous Coward]

Your number is divisible by 2. And I did that in my head!

Re:Article Title

[zCyl]

It may not be prime, but it's possible. Aren't all numbers "possible" prime numbers?

Not the ones ending in 4... :)

Re:Article Title

[raoul666]

*Ahem*

I'm gonna go out on a limb and say if it ends with a 4, it's not gonna be prime...

Re:Article Title

[Anonymous Coward]

And it's pretty obvious that a "number" that contains a letter isn't a prime...

Re:Article Title

[Anonymous Coward]

or that is has an 'o' in it...

Re:Article Title

[Joe at Axual]

So, I can conclude a at least two things from the comments so far: 1. Slashdot users actually observed the number and made computations. 2. Any number is in fact a possible prime number until it's observed and an operation is applied. Thanks for contributing to my experiment. Joe at ewizmo.com

Re:Article Title

[lucifer_666]

No, what's being demonstrated is that should a number end in 4, it is in fact *not* possible for it to be prime.

OMG

[voxel]

And the number 1 has 1 digit, which is prime too! Oh man, I can't take it anymore, someone make it stop!

Re:OMG

[Aewyn]

OK...

By definition, a prime is an integer with exactly two different positive integer factors. So 1 is not a prime.

Re:OMG

[Anonymous Coward]

By definition, a prime is an integer with exactly two different positive integer factors. So 1 is not a prime.

No, but 2 is. :^)

Prime # Bear

[DaFallus]

The Prime Number Shitting Bear is still my favorite way to count primes.

Re:How do they check a number that big for primene

[Jerry Coffin]

Not to be overly harsh on your post, since in truth there are a dozen other posts in this story which are equally wrong, but this post is just plain wrong.

Not at all -- you're absolutely right. As sometimes happens, I hit "preview" about three times to fix minor problems, and then three minutes after I hit submit, realized my brain had dredged up the wrong thing entirely, and I'd made a massive blunder...

In particular, the special number field sieve runs slower than polynomial time, so running it on a number of 10 million digits is wildly impractical.

I doubt that run-time would be the real limitation. I suspect the size of the factor bases would become prohibitive first. I suppose (in a way) you could look at this as a time problem, since you could theoretically store them largely in slower storage, but in doing so the problem would be (primarily) with access speed, not the complexity of the algorithm.

First Prime Factorization Post

[Anonymous Coward]

...

You didn't print the number in the article, you insensitive clod! How is 2*2*3*75011 meant to gre^H^H^Hfind it and start factorizing?

WHO CARES???

[Anonymous Coward]

Honestly, there are too many distributed computing projects that are a complete and utter waste of resources. Prime numbers? What the hell are we going to do with a 10 million digit prime number? It's like a geek pissing contest! Why aren't we all on Folding@Home or some other project that is devoted to helping the human race?

lame comment follows

[theguywhosaid]

2^2-1 = 3
3 == 11

I guess you are wrong and all primes really do follow the form 2^2-1 !!!! Fields Medals for everyone!!!!

You get

[geekoid]

to give up all your base....

Server vs. browser

[benhocking]

Ah, but that'd no longer bring the server down, would it? :)

Also, it would help to discourage this festering practice of RTFA. When did slashdotters start doing that?

I Don't Get It

[Anonymous Coward]

It is really easy to write a program that will calculate large prime numbers; and it doesn't take months or years to run. It only took about 3 minutes to find a 100,000,000 character number and 6 minutes to write the file..
http://members.mac.com/shaffer.david/prime.zip

The number is a 1 with 99,999,998 0s and a 3. And it only take a few more minutes to find the next prime number. The algorithm is O(n) when using a char array to represent the number.

I dunno, maybe I don't understand the problem.

Ya want a big number? Start with a 1, add a bunch of 0s and end with a 1. Test if it is divisible by 7. If not, IT'S PRIME! What's the big deal?

Re:I Don't Get It

[Anonymous Coward]

10001 = 73137

Re:I Don't Get It

[Anonymous Coward]

Sorry, the URL (w/ code, etc) is..

http://homepage.mac.com/shaffer.david/prime.tgz

Prime number posters

[CommandoB]

[shameless plug]

Perfectly Scientific, Inc. sells posters of these primes, printed explicitly (in provocative notation?). If printer technology allows, there will soon be one for this 10 million digit beast too.

They're great if you're looking to test that macro lens on your digital SLR, or if you're just curious what 8 square feet of 1pt font looks like (it looks like a gray slab).

Or you could find your own primes. There's some open source code for the interested. [/shameless plug]

Fun for the whole family. Sort of.

This is all good and fine, but...

[Spunken]

...why must all prime-numbers be generated by computors nowadays?
Can humans be said to be responsible for them when the computors did it?
What happened to that great tradition of searching for new prime-numbers by hand?
I mean, how hard can it be?

What did you say? 10 million digits? Well, is it that much really?

Wanna make a quick buck?

[rice_burners_suck]

There should be a billion dollar prize for finding the first prime number with over a billion digits. That shouldn't be too difficult to do with a pocket calculator, pencil, and paper.

Oh no!

[Anonymous Coward]

Kate Bush will have to sitt down and make another PI song!
(The first song was not bad actually...)

1,000,000th /.er

[omahajim]

US$50k for the first prime over ten million digits. Big deal - what will the person grabbing slashdot UID 1,000,000 receive? We're up to about 940400 or so now. Shouldn't be long.

Listen, I'm just as much a geek as all of you...

[Atario]

...but if you keep this up I'm going slap you all at once, Moe Howard style.

(And, just to cut you off: yes, I know the number of Stooges, three, is a prime.)

Note to self: People don't read disclaimers.

[SeanDuggan]

Sometimes I really wonder about people. I clearly marked it as tongue-in-cheek humor. Meh.

Although, really, I have my doubts about ever finding a "cure for cancer" short of developing nanobots that rebuild cells to conform to set specifications. Cancer is too random and, well, as I said before, it's pretty much built into our systems. Specific strains can sometimes be combatted, but it's generally a matter of killing all of the tissue in the area whether it's by biopsy, chemotherapy, radiation, or other drugs. We'd might as well be searching for prime numbers.

There is a message in there...

[Snaller]

...if you rearrange the numbers in the correct way you get a binary pattern of the letters: SO LONG AND THANKS FOR ALL THE FISH!

...Then it must be: 42!

[Tune]

The answer to Life, the Universe, and Everything must surely be the answer to finding this new prime number as well, right?!

(Unfortunately, Earth will probably be destroyed before anyone can read this post.)