Forgot your password?
typodupeerror

New Record Prime Found 112

Posted by kdawson
from the mersenne-is-a-gimp dept.
An anonymous reader writes, "The GIMPS project has found a new record prime. 2 ^ 32,582,657 - 1, clocking in at over 9 million digits, is a Mersenne prime, as were the last few record primes. Here is the 9-megabyte decimal expansion."
This discussion has been archived. No new comments can be posted.

New Record Prime Found

Comments Filter:
  • by tygerstripes (832644) on Thursday September 14, 2006 @08:47AM (#16103302)
    ...Please move along."

    That's what /. said when I first clicked the story, anyway. I immediately assumed it had been commandeered for use in US military codes...

    </tinfoil hat>
  • They say that they are on a winning streak and that lightening strikes twice etc, well I just say they are continuing running a program which can handle large numbers.
    The longer they run it the more they will find.
    They are getting all the records because noone else is "trying" as hard.

    Good luck that they get the 10million digits, but its just a pissing competition as far as I can see.
    They win 100,000 from the EFF for breaking it, but the computational power and time wasted has to be getting close to that it
    • > Good luck that they get the 10million digits, but its just a pissing competition as far as I can see.
      Yeah, all that computing power could be doing something useful, like say, helping the NSA and other TLAs break encryption keys. Probably under the cover story that they're 'searching for extraterrestrial intelligence'... Yeah, like that'll ever happen.. :P
      • by QuantumG (50515)
        Or, ya know, estimating protein folding, something that could contribute to medical research and thus save lives one day.
    • I've been running prime95 on my Windows machine for 6 or 7 years. I think it's WAY more useful and productive than SETI, and I'm not willing to use my spare cycles to enrich other peoples patent portfolios. I think being able to produce a nine million digit prime number by memorizing eight digits is a pretty cool thing.
      • by LehiNephi (695428)
        I can't argue about the novelty of being able to "produce a nine million digit prime number by memorizing eight digits", but I'll take issue with your comment about the patent portfolio. Stanford have stated [stanford.edu] that they'll make the results available to everyone.

        I run Folding@Home since my computers are on 24/7 anyway--and if it leads to a cure for cancer/leukemia/Hodgekins'/alsheimer's/whatever-ot her-cancer-related-disease, I won't mind if someone makes money off producing the cure.
      • by freakmn (712872)
        Prime95 is so outdated. Try the latest in prime number finding: The Prime Number Pooping Bear [surfeu.fi]. I won't believe this number until the bear confirms it for me.
      • They are now starting to build higher-resolution models to help predict specific risks for certain regions in greater detail.
    • by fatphil (181876)
      [Note - if I appear partisan, it's because I'm a prime-hunter myself]

      I don't think that it's fair to say that no-one is trying as hard, as many people are, it's just a matter of quantity of effort, rather than quality of effort. GIMPS is huge (and maintains a momentum because of that - people join it because it's the biggest).

      So electricity-wise, you're not just right, you're so right that you're completely wrong! (Did that make sense?) It we pretend that on average they have been running 50000 machines for
  • Woo Hoo! (Score:3, Funny)

    by nystagman (603173) on Thursday September 14, 2006 @08:54AM (#16103355)
    2 ^ 32,582,657 - 1th post. Eventually...
  • by johnfink (810028) on Thursday September 14, 2006 @09:03AM (#16103419)
    I have the same combination on my luggage!
    • by blinder (153117) *
      darn it, no mod points. i did, however, post a pleading for mod points in my journal, for this post. yes, an old joke, but very funny... especially in this context.
  • So what's the biggest known prime number that's not a Mersenne number? Wikipedia's "Prime number" article [wikipedia.org] states that it's a prime Proth number [wikipedia.org], but what about the biggest prime that's not of any special form? Or is that illegal [wikipedia.org] to discuss on Slashdot, a server on US soil?

    • Re: (Score:2, Insightful)

      by Anonymous Coward
      what about the biggest prime that's not of any special form?

      I'd tell you, but it doesn't fit in the comment limits.
      • Re: (Score:3, Funny)

        by nacturation (646836)
        I'd tell you, but it doesn't fit in the comment limits.

        Just list the factors... I'm sure we can do the math ourselves.
         
    • How do you define a prime number that's not of a special form? Wouldn't such a definition make the prime of a special form?
      • How do you define a prime number that's not of a special form?

        I was operating under the assumption that consensus among pure mathematicians creates the list of formulae known to produce a lot of large prime numbers from a few arguments. These include Mersenne numbers (where Mersenne(n) = 2^n - 1 for all prime n) and Proth numbers (where Proth(k, n) = k*2^n + 1 for all odd k < 2^n). I was looking for primes that aren't as compressible.

        • Although I could argue that a lack of compressibility might be special. ;) Still, regardless of definitions, it would be interesting to find such a prime, or to postulate about their existence. Is there a postulate that such a prime must exist? Is it possible that all primes have a certain level of "compressibility"?
          • Although I could argue that a lack of compressibility might be special.

            Kolmogorov complexity [wikipedia.org] is an objective measure of compressibility. However, this measure is not computable.

            Still, regardless of definitions, it would be interesting to find such a prime

            Finding such a prime is straightforward. Take a block of true random data (which is incompressible by definition), append an odd integer, and then increase that odd integer until primality tests such as ECPP [wikipedia.org] come back true. This is the technique used

            • by djshaffer (595950)
              I can compress any prime number, given sufficient compute time.

              2 => 1
              3 => 2
              5 => 3
              7 => 4

              See? 2 is the 1st prime, 3 is the second. Just make sure you haven't missed any as you get to larger primes. As a tradeoff, the compression factor eventually gets very high.
            • Truly random data definitely has a chance of being compressible. For example, there's a 1 in 2^50 chance that a random, fair Bernoulli process will generate the string /1{50}/. If I use a biased Bernoulli process, say with p=0.999, I can generate such a string with much better odds. Specifically, there's more than a 95% chance that I'd generate that string, and there's even a 37% chance that I'd generate /1{1000}/, for a string of size 1,000.

              I read the piece on Kolmogorov complexity, and although it's the

              • Despite the well-known issues with the halting problem, this can actually be done trivially for a program of maximum size n if you have a machine of state size 2^n (for a binary language) and a lot of patience.

                Um, that's only true if the machine the program is being run on is limited to n binary states. So, for a true Turing machine, I think that actually calculating the Kolmogorov complexity is not even theoretically possible, unless the "language" specification stipulates a maximum amount of memory to u

              • If I use a biased Bernoulli process, say with p=0.999, I can generate such a string with much better odds.

                I was operating under the assumption of a fair Bernoulli process. In the case of something in any way biased, the device driver will likely convert it to a lower-bandwidth fair Bernoulli process by hashing blocks of raw data and returning one output bit for several raw bits.

                (Despite the well-known issues with the halting problem, this can actually be done trivially for a program of maximum size n if

          • by flooey (695860)
            Still, regardless of definitions, it would be interesting to find such a prime, or to postulate about their existence. Is there a postulate that such a prime must exist?

            There are infinite primes, we know that. Whether every single prime can fit into some kind of classification, though, we don't know. It's conceivable that there might be, but it seems incredibly unlikely, especially given things like the classification of all finite simple groups (most of which fall into a few neat categories and then t
          • Re:A good definition (Score:4, Informative)

            by jd (1658) <imipak @ y a h o o .com> on Thursday September 14, 2006 @05:19PM (#16108805) Homepage Journal
            Any natural number that is a prime can be split into a sum of natural numbers (where the number of elements in the sum is at least 2) for all natural numbers that are primes other than 1. It is always possible to have one of those numbers non-prime (except for the natural numbers 2 and 3). By dividing the non-prime numbers into the prime factors, and then repeating the process, you can split the original number into some expression e, where if we swap the constants for variables (or unknowns) the general form is E. There will be a number of possible values of E, so I'll call the set of all possible expressions for that prime {E}. Ok, now let us say that the set of all possible sets of expressions for all possible primes is {{E}*}. Because I'm allowing any general solution, there will be a finite number of generalized solutions (ie: using undefined constants) but potentially an infinite number of specialized solutions where the constants are all defined.


            5, for example, is a solution to the general formula A(x^C)+D, sum(x)+C, Cx+D, and so on. (Because A, C and D are constants, they would need to be the same constants for all primes you apply the expression to. Otherwise, you've not really generalized or simplified anything.) It is easy to show this has an infinite number of special solutions - pick any value of C and for any equation with D in it, simply subtract/add the necessary value to give you the prime you want.


            The original question, then, is whether there is any prime number (other than the three special cases listed) for which {E} /\ {{E}*} = {E}. That would be a prime for which no possible expression to derive it, no matter how generalized, can ever be used to derive any other prime number. Intuitively, it seems apparent that no such prime exists, as there will be many primes with an infinite number of solutions that do not overlap. However, there are also an infinite number of primes and I have no obvious way of proving that the infinite set of primes is a perfect subset of the infinite number of derivations.


            Let us define something else, which is #({E} /\ {{E}*}) - the number of general solutions for a given prime that are also general solutions for at least one other prime. The larger the prime, the larger the number of possible generalized solutions, because the larger the number of subcomponents you can break it into which can be turned into equations. However, the number of overlaps is not so easily determined. It is very easy to imagine a large prime in which most general forms are the same as only a few other primes, whereas a smaller prime might overlap with a great many primes in a great many ways. It is also possible to imagine a set of primes in which all primes in that set have the same general form, but no member has a general form that is the same as any outside of that set.


            (It is easy to prove that there exist two primes which have no general form in common, as that is simply the same as the proof that no general equation for primes exists.)


            This leads to interesting possibilities - "islands" of primes that are totally disconnected from all other primes, "peninsulas" where you almost have an island but some perfect subset of the cloud does have a general form in common with other primes, "mountains" where you have a massive number of general forms totally in common with a large number of primes, and so on.


            If you were to draw out the interrelationships between primes as a topology, what do you see? A random blob? A sea of islands? Multiple large masses that are otherwise disconnected? If islands, or multiple disconnected continents, exist in prime number space, does this mean that prime numbers aren't a single, definable set of numbers at all, but multiple concepts that should (in general) not be treated as the same at all? Will the map indicate that we can generalize the definition of prime number in a useful way, that the concept can be usefully extended and meaningfully applied outside of the natural numbers?

      • How about this: What is the largest known prime number where all previous prime numbers are also known?

        Ed
  • Perfectly Scientific, Dr. Crandall's company which developed the FFT algorithm used by GIMPS, will make a poster you can order containing the entire 9.8 million digit number. It is kind of pricey because accurately printing an over-sized poster in 1-point font is not easy!

    And to think, all I had was a Ghostbusters poster when I was growing up.

  • If they announced finding a new large prime number, and then later realized the number was even, and they hadn't noticed that. (I know, this one is one less than a power of two, but just hypothetically.)
    • by x2A (858210) on Thursday September 14, 2006 @09:29AM (#16103668)
      Or when converted to binary, it turned out to be an mp3 of the latest song from [insert-RIAA-label], and so they banned distribution of it :-p

      • by kestasjk (933987) on Thursday September 14, 2006 @10:01AM (#16103994) Homepage
        I know that was a joke, but this gives the impression that this number in binary is a long stream of 1's and 0's.

        Seeing as 2^n is [1 followed by n 0's] in binary, and [1 followed by n 0's] minus 1 is [(n-1) 1's], this number in binary will just be 32,582,656 1's, which isn't decodeable as an MP3.
        • Re: (Score:3, Funny)

          by r00k123 (588214)
          Could be Bjork...
        • Re: (Score:2, Funny)

          by thelost (808451)
          really? To me that sounds just like Justin Timberlake's latest stuff :S
        • Does anyone know how these numbers get parsed out? I wonder if we are using the right formulas? As in I wonder if thinking in a different base number (2?) could help us find a much more precise formula for finding this? This prime was pretty simple-- a couple million 1's in a row. Maybe there's one for a couple million 10's in a row?
          • I hope you're not suggesting that anything ending in a zero, in any counting system, could ever be a prime?
          • After reading your comment, I can't really say anything other than.. go do some university level maths courses, and come back.

            Basically, mersenne primes are of the form (2^p)-1, where p is a prime. The reason that these numbers seem to keep turning up as really big primes is that there is a very special test which checks if just this type of number is prime. The Mersenne project is searching it's way through all possible candidates to see if it can find some big primes.
        • by Cragen (697038)
          Silly question (cuz IANAM): Are most (many, few or all) binary numbers that have all 1's in the number prime? Just curious. Cragen
          • by Meostro (788797)
            A Mersenne number is exactly what you're talking about, a long string of binary 1's.

            Mersenne numbers are of the form 2^N - 1, which is essentially a binary string of N consecutive 1's. For example, the tenth Mersenne number - aka M(10) - is 2^10 - 1, which is 1023. The binary representation of 1023 is 1111111111.

            The answer to your question is on the GMPS homepage [mersenne.org]:

            When looking at the exponents, we expect only 1.78 Mersenne primes between powers of two, and prior to 2003, a maximum of 3 Mersenne primes were

      • >Or when converted to binary, it turned out to be an mp3 of the latest song from [insert-RIAA-label]

        How about if I released it as a record? Would it then become illegal?

        I can't believe it would sound any worse than the rubbish kids are listening to today :o)
    • by Billosaur (927319) *

      If they announced finding a new large prime number, and then later realized the number was even, and they hadn't noticed that.

      Even funnier -- they name it "Optimus."

  • ... what possible applications do Mersenne primes of this size have? Is this just some big 'penis envy' thing, or are there actually uses for these?
    I mean, Dnet have pretty much proved that any encryption key less than 64 bits is hopelessly insecure (ISTR they're working on 72 bits at the moment), and they did the Optimal Golomb Rulers search, but what possible use does all this stuff have? Are we just looking for things that are neat, but have no use in the real world?
    Folding@Home is still pretty neat th
    • Sometime in the future this too will pay off. Hope for the best and keep looking for new stuff.
    • Re: (Score:3, Informative)

      by Ruzty (46204)
      Folding@Home is still pretty neat though - the whole "use your spare CPU cycles to (potentially) find cures for various nasty things"

      I think you should have said:
      Folding@Home is still pretty neat though - the whole "use your spare CPU cycles to (potentially) find cures for various nasty things and enrich the patent portfolios of drug manufacturers"

      HTH HAND
      -R
      • Point taken. Well played, sir.

        At least finding ETs doesn't involve enriching some MegaHuge PharmaCo's patent portfolio...

      • by Magada (741361)
        You missed one. It should be "use your spare CPU cycles to (potentially) find cures for various nasty things and enrich the patent portfolios of drug manufacturers AND (possibly) help design the next Black Death".
  • Expand it yourself (Score:4, Informative)

    by Coppit (2441) on Thursday September 14, 2006 @09:48AM (#16103875) Homepage

    If you want to expand the number on your machine, run this:

    perl -Mbignum -e 'print 2**32582657 - 1'

    If it takes too long for you, you can also have perl print an approximation:

    perl -e 'print 2**32582657 - 1'

    • by B5_geek (638928)
      For real fun add the 'time' command to benchmark your PC's
    • by Pharmboy (216950)
      I just wrote a lazy hack to get a list of primes

      #!/usr/bin/perl
      for ($x=1;$x>0;$x++){
      if(`factor $x|grep '$x: $x'`){
      open(LOG,">>log.txt");
      print LOG "$x\n";
      close(LOG);
      }
      }

      It's running in the background on my home linux router, an older AMD XP 2700+. Already up to 334157 and the load is only 2.50. Wonder how long it will take until I get to 2^32582657? ;)

      • by dylan_- (1661)
        I suspect you'll run out of disk space first! :-) Out of curiosity, what filesize and prime are you at now?
        • by Pharmboy (216950)
          Good point! Up to 461207 and a 256k log file. Its on a smaller partition, but if I have to, I can change the value of the first $x to the last prime, and move it over to another partition. Got almost a terrabyte total on the machine, and half of it free.
          • by Pharmboy (216950)
            To follow up: Found 141,739 primes, the largest being 1,895,693 before I decided I needed the CPU cycles for something else. (one prime for every 13.3745... numbers). Log file is about 1mb. It took about two hours to get to that number. Might take a little longer to get to a new record. ;)

            Then, all i have to do is edit the executable file and put $x=(1895693 +1) to pick up where I left off.
            • by crownrai (713377)
              Don't you mean put "$x=(1895693 +2) "?

              You're not checking even numbers are you?
              • by Pharmboy (216950)
                um, if you look at the code, I'm checking all numbers. It was a full 30 seconds worth of code. I guess I should have done:
                for ($x=1;$x>0;$x=($x+2))
                ...duh me. Oh well, it has that line NOW.
                • by vistic (556838) *
                  In addition, I wonder if there's an efficient way to skip products of any of the prime numbers already found.
                  • by Pharmboy (216950)
                    In the program, I guess you could assign $x as the value of the highest known prime, but I think the average 32 bit Linux installation would have run out of precision before it got to that value.
    • by FooAtWFU (699187)
      If it takes too long for you, you can also have perl print an approximation:
      perl -e 'print 2**32582657 - 1'
      Okay. I'll try that. :)
      <tom@eh ~ $> perl -e 'print 2**32582657 - 1'
      inf<tom@eh ~ $>
    • by doti (966971)
      If it takes too long
      How long is too long?
      I have it running for whole three hours now, still no result.
      relevant info from /proc/cpuinfo:
      model name : AMD Opteron(tm) Processor 248
      cpu MHz : 2193.796
      cache size : 1024 KB
      bogomips : 4377.80
  • by Mister Impressive (875697) on Thursday September 14, 2006 @10:05AM (#16104025)
    Doesn't stand a chance against the one true prime...

    OPTIMUS PRIME!
  • The Actual Number (Score:4, Informative)

    by neonprimetime (528653) on Thursday September 14, 2006 @10:06AM (#16104038) Homepage
    View it here [isthe.com] in it's 12mb text form!!!!!!!!

  •     *head explodes*

  • I had just been reading up about the Japanese Wii launch dates and I thought this article title was "New Metroid Prime Found". Blast!
  • Okay, I know what a Prime number is, I passed high school. And this number is huge.

    My question is, can someone describe to me in SIMPLE terms what a Mersenne prime is?

    Do we really do math where we need to discover prime numbers this big? I mean, its like trying to compute pi. I mean, once you take PI out a few decimal places, its as accurate as most people need it. Do we really need super computers that do nothing better with their time than calculate this kind of stuff?

    I am sorry if I sound ignorant, but i
    • My question is, can someone describe to me in SIMPLE terms what a Mersenne prime is?

      f(x)=(2^x)-1. "f(x)" is prime. Another way of thinking about it is like this. In binary representation, all the bits are set to "1". There are a few of these for small x, but as it gets larger, the primes are few and far between. One of the issues in mathematics is figuring out if there is a "last" Mersenne prime. Is there one so big there isn't one larger of this special form? I doubt it, but nobody can prove it one way or

It is clear that the individual who persecutes a man, his brother, because he is not of the same opinion, is a monster. - Voltaire

Working...