Slashdot Mirror
New Record Prime Found
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."
...Please move along."
/. said when I first clicked the story, anyway. I immediately assumed it had been commandeered for use in US military codes...
That's what
</tinfoil hat>
Meta will eat itself
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 itself.
liqbase
2 ^ 32,582,657 - 1th post. Eventually...
Theory and practice are the same in theory, but different in practice.
hmmm... that's not gonna fit in an int is it?
I have the same combination on my luggage!
So what's the biggest known prime number that's not a Mersenne number? Wikipedia's "Prime number" article states that it's a prime Proth number, but what about the biggest prime that's not of any special form? Or is that illegal to discuss on Slashdot, a server on US soil?
And to think, all I had was a Ghostbusters poster when I was growing up.
Reviewing just the first hour of video games.
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.)
Apology to Ubuntu forum.
... 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 though - the whole "use your spare CPU cycles to (potentially) find cures for various nasty things" concept is pretty neat, and no-one can say that saving lives isn't worth spending a few clock cycles on.
SETI@Home I'm still not sure about. Yes it would be nice to find 'intelligent' creatures on other planets, but what are we going to do if we find them? Chances are they're going to be at least a few light-years away, so the round-trip times for radio signals are going to be pretty severe...
I ca... Oh crap.
"If you make people think they're thinking, they'll love you; But if you really make them think, they'll hate you." - DM
Seriously.. how do you compute? I want to check for my self.
Um, try that with n=4, and you'll see that your assumption isn't correct...!
2^4-1=15
Try n=8.
One CS student VS 893 DOS games: Let's play oldies
That is wrong for n=4. 2^4-1 = 16-1 = 15 = 3 * 5 Somehow, somewhere there is a math teach spinning on his/her grave right now.
2^4 - 1 = 15 = 3*5.
Actually no. Not all numbers in the form of 2^n-1 are prime. There are only 44 known numbers in that form that are prime.
There are 10 types of people in the world: those who understand binary and those who don't.
Try n=4
Not so, I'm afraid. All Mersenne primes are one less than a number which is 2^(prime) - but the converse is not necessarily true.
Meta will eat itself
2^4-1 = 15 = 3*5 Not prime
---- aut viam inveniam aut faciam
There are various reaons to think that numbers of the form 2^n-1 are a good place to look for primes, but they are certainly not all primes. Here are the first counter examples:
2^4 - 1 = 16 - 1 = 15 = 3*5
2^6 - 1 = 64 - 1 = 63 = 3*3*7
2^4 - 1 = 15 = 5 * 3
Ha Ha!
Hey everyone! Let's massacre the parent! Bonus karma points to the one who can shoot down the suggestion the best!
I almost feel silly doing this...
2^4=16
16-1=15
15=3x5
-knewter
I thought that all numbers in the form 2^n -1 are prime - If I am correct, what's so new about this number? -Nicolas
Nope, most of them aren't:
(2^3)-1 = 8 - 1 = 7 (prime)
(2^4)-1 = 16 - 1 = 15 (not prime, 3, 5)
(2^5)-1 = 32 - 1 = 31 (prime)
(2^6)-1 = 64 - 1 = 63 (prime)
(2^7)-1 = 128 - 1 = 127 (prime)
(2^8)-1 = 256 - 1 = 255 (not prime, 3, 5)
etc..
Mersenne primes are simply primes that have this form, but not all numbers that have this form are prime. For example, 15 = 2^4 -1 and is not prime.
Also, for a number to be a Mersenne prime, the 'n' from 2^n-1 must be prime (according to Mathworld).
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?
Ben Hocking
Need a professional organizer?
Good lord, no.
Take 2^4 - 1 = 15 = 3 * 5
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'
Um, how about, RTFA? ... The third link gives you a breakdown of the history.
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.
If a divides n, then 2^a-1 divides 2^n-1.
.... 2^((n/a)*a) == 1.
So for 2^n-1 to be prime, n itself must be prime.
Quick proof - consider the values of 2^i modulo (2^a-1) for i=0..n,
You'll notice that 2^0 == 2^a == 2^(2a) ==
i.e. 2^n-1 == 0 (mod 2^a-1)
Note, however, that it's a necessary condition, but is not sufficient.
There are plenty of prime p such that 2^p-1 is not prime.
See http://www.primepages.org/
FatPhil
Also FatPhil on SoylentNews, id 863
Doesn't stand a chance against the one true prime...
OPTIMUS PRIME!
Let the commencement BEGINULATE!
View it here in it's 12mb text form!!!!!!!!
*head explodes*
Note: This sig contains nine S's, nine I's and five O's which... means absolutely nothing.
RTF Post. I was referring to the parent who thought all numbers of the form 2^n-1 were prime. Naturally, slashdotters ate him up and spit him out.
1 03985
I say bonus karma points to this guy:
http://slashdot.org/comments.pl?sid=196548&cid=16
I had just been reading up about the Japanese Wii launch dates and I thought this article title was "New Metroid Prime Found". Blast!
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"?
Ben Hocking
Need a professional organizer?
>Or when converted to binary, it turned out to be an mp3 of the latest song from [insert-RIAA-label]
:o)
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
Open Source Drum Kit, LPLC deve board - mjhdesigns.com
> (2^6)-1 = 64 - 1 = 63 (prime)
7*9 = 63
No power on Slashdot so great as the need to correct others' mistakes.
Ok, to actually be helpful here instead of being the 16th person to say 15 isn't prime (seriously, you should all be marked redundant) maybe the parent was thinking of 2^(2^n)+1, which is a Fermat Prime. Unfortunately, not even Fermat Primes are actually prime, Fermat just thought they were when he discovered them.
How about:
Prime1*Prime2-2? (so long as neither one of them is '2')
Help! I'm a slashdot refugee.
63 isn't prime.
Exactly. And 15 is divisible by 2.4 and 6.25, silly people.
Kolmogorov complexity is an objective measure of compressibility. However, this measure is not computable.
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 come back true. This is the technique used to find the first prime that may be illegal to publish.
Mod parent up: poster explains what conditions are required for a Mersenne-form prime.
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?
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 theoretically a well-defined measure (given a particular programming language or other form of interpretation), in practice it's doubly exponentially difficult to calculate. I'd have to generate every possible program of size less than n (where n is the actual Kolmogrov complexity) in order to verify that n is in fact the Kolmogrov complexity. Worse yet, for those programs that don't halt (and are of size less than n), I'll have to know that they don't halt. (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.)
Ben Hocking
Need a professional organizer?
5*7-2 = 33 = 3*11
Trust me. If it was this easy, we'd have heard of it long ago.
That might be arbitrary enough to qualify as non-special since it will only be "special" for a limited time.
Ben Hocking
Need a professional organizer?
Nope.
7 * 5 = 35
35 - 2 = 33
33 = 3 * 11
2 * 5 = 10
10 - 2 = 8
8 = 2 * 4
7 * 11 = 77
77 - 2 = 75
75 = 5 * 15
Just to cite a few.
Everything I say is a lie. Except that... and that... and that, and that, and that, and that... and that.
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 use (perhaps relative to the size of the string being examined). In my opinion, this is not an unreasonable expansion of the definition, however. E.g., if it requires 2 Gigs of RAM and/or hard drive space to compress a 10,000 bit number down to a 1,000 bit program, I'm not sure if it's fair to say that the complexity is only 1,000 bits.
Ben Hocking
Need a professional organizer?
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.
"A lot of patience"? Living organisms have little patience in this universe. True, halting is computable for linear bounded automata, but not in the human lifetime or even in the lifetime of the universe for a reasonably sized program string. By 10^15 years, it is expected that even the stars will die, providing no more energy to run the computation.
I was responding exactly as you requested - The parent had missed the link "Marsenne prime", which provides an article explaining that some 2^n-1 numbers are not primes and who proved what. The original post already provided Mr. "Help" with the info he needed. Don't worry - but I'm sure I didn't even need to point that out; you've made him feel plenty stupid already.
(2^6)-1 = 64 -1 = 63 = (9 * 7) (not prime)
Tubby or not tubby. Fat is the question
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 it seems to me that sometimes people just get worked up about stuff that we don't really need. I mean, really, yeah, its cool that we found a prime number this large, but whats the point?
In any prime base, 10 is a prime number.
Go figure., gotta love math
Ergo, a large number a /.ers would correct Fermat given the opportunity to do so.
...the future crusty old bastards are already drinking the Kool-Aid.
They are now starting to build higher-resolution models to help predict specific risks for certain regions in greater detail.