2^57885161 - 1

February 7, 2013 3:10 PM

The new largest prime number has been discovered! Why is this awesome? Because it is more than 17 million digits long. Also, the article contains quotes from mefi's own escabeche.
posted by klausman (76 comments total)

Someone posted that number to facebook yesterday, and I immediately checked to see if 57885161 was prime, because I'm the kind of dork who knows what a Mersenne prime is.

Neither of these purses is prime.

I don't know who Elizabeth Landau is, but I think I might love her.
posted by axiom at 3:23 PM on February 7 [4 favorites]

I immediately checked to see if 57885161 was prime

2^n - 1 is prime => n is prime. Of course the converse isn't true, wherein lies the rub.
posted by kmz at 3:27 PM on February 7 [1 favorite]

Right. I should've been clearer; the number was posted without any context, but the format, 2^57885161 - 1, made me suspect it was a Mersenne prime. Because who just posts 2^n -1 for some random n?
posted by axiom at 3:31 PM on February 7 [1 favorite]

I like that the article points out that the dollar amounts in the prize money are not themselves prime.
posted by suprenant at 3:34 PM on February 7 [5 favorites]

Biiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiig int
posted by mattoxic at 3:59 PM on February 7 [13 favorites]

I like the way the CNN article says:

It is indeed massive, more than 17 million digits long. A text file of the entire number contains more than 22 megabytes of information.

posted by DarkForest at 3:59 PM on February 7 [7 favorites]

I can appreciate this, and I was once again mind-boggled the other day when looking at a comparative illustration between planets in our solar system and the largest stars. I am reminded that my brain is very weak.

This should not come as a surprise, however, because if you hand me a calculator I will probably spell BOOBS with it instead of doing any actual work.
posted by jimmythefish at 4:01 PM on February 7 [8 favorites]

30 days for comment threads, people. We can beat that number here!
posted by Burhanistan at 4:03 PM on February 7 [1 favorite]

Of digits, or the number itself?
posted by Rustic Etruscan at 4:04 PM on February 7

Of digits, or the number itself?

If it's the number itself, we could take several approaches.

- (2^57885161 - 1) + 17. This may not be prime, but 17 is pretty dodgy and it'll take them long enough to refute that it'll buy us some good glory time.

- The 7 year old approach: The next prime number after 2^57885161 - 1.

- Ask Siri, and maybe get one of those battery pack cases for the extra juice to let her think longer if you have to unplug to go get burgers.

That's all I have people.
posted by jimmythefish at 4:11 PM on February 7

I like the way the CNN article says:

Hey, you can't assume 1 character = 1 byte anymore. Some of those digits might be Unicode.
posted by aw_yiss at 4:14 PM on February 7 [3 favorites]

Is anyone else eventually getting redirected to a facebook error page?
posted by Lemurrhea at 4:14 PM on February 7 [1 favorite]

The 7 year old approach: The next prime number after 2^57885161 - 1.

Or go the other way: If you're so smart, what's the smallest Mersenne prime?!

It's 3.
posted by axiom at 4:16 PM on February 7 [2 favorites]

Any math people understand why the following is true:

"The formula named after him is 2 to the power of "p" minus 1, where "p" is a prime number. This doesn't always yield a prime, but the result has a greater chance of being prime, and it's easier to verify whether it's prime"

If primes are truly random, why does this formula lead to a higher probability that the number will be prime, beyond that it will just be an odd number or something? Is it generally accepted among mathematics experts that no one will ever find a formula for predicting prime numbers?
posted by gagglezoomer at 4:18 PM on February 7

Is this meaningful and useful or is it masturbatory mathematical macho posturing?
posted by xmutex at 4:20 PM on February 7 [1 favorite]

I'm pretty sure primes aren't "truly random". I remember in my undergrad days seeing formulae that could calculate the nth prime.

...the problem being that they were impractical in terms of computing power for anything other than the ones we already knew.
posted by Lemurrhea at 4:28 PM on February 7 [1 favorite]

Some of those digits might be Unicode.

Or maybe CNN uses old PDP-11s and they decided to encode the file in octal digits.
posted by DarkForest at 4:29 PM on February 7 [1 favorite]

Is this meaningful and useful or is it masturbatory mathematical macho posturing?

Why can't it be both?
posted by escabeche at 4:35 PM on February 7 [11 favorites]

If primes are truly random, why does this formula lead to a higher probability that the number will be prime, beyond that it will just be an odd number or something? Is it generally accepted among mathematics experts that no one will ever find a formula for predicting prime numbers?

My serious math days are long since over, but I think maybe the reporting here was a little weak. Mersenne primes are rare (that is, 2^p-1 is not often prime), but I think the trick is that 2^p-1 is at least a starting point for finding (very large) primes, as opposed to just (say) selecting an odd number and testing it for primality. Random selection of odds is generally going to be a bad strategy for large values of N, since the number of potential factors grows the higher up you get, so primes get spaced further and further apart.
posted by axiom at 4:38 PM on February 7 [1 favorite]

why does this formula lead to a higher probability that the number will be prime, beyond that it will just be an odd number or something?

I actually had to go look this up when I talked to Landau -- I'm a number theorist, but not exactly this kind of number theorist. There's a generally well-believed heuristic due to Lenstra, Pomerance, and Wagstaff which suggests that a Mersenne number with N digits is about (log N) times as likely to be prime as is a random number with N digits. The derivation of that heuristic is discussed here.
posted by escabeche at 4:39 PM on February 7 [9 favorites]

This discovery has great timing, beginning of the semester for my mathematician's non-majors number theory class - they were excited to hear about this.
posted by LobsterMitten at 4:43 PM on February 7

This should not come as a surprise, however, because if you hand me a calculator I will probably spell BOOBS with it instead of doing any actual work.

Give me a dollar if 80085 appears somewhere in the decimal expansion of this number. I'll give you all the money in the world if it doesn't.

This bet actually favors me.
posted by madcaptenor at 4:46 PM on February 7 [2 favorites]

It is indeed massive, more than 17 million digits long. A text file of the entire number contains more than 22 megabytes of information.

Next time, it might be a good idea to leave out the commas separating every three digits.
posted by The Tensor at 4:50 PM on February 7 [13 favorites]

I noticed a strange little chain in the list of known Mersenne primes (M_p):

3 is a Mersenne prime; M₃ is also a Mersenne prime equal to 7; M₇ in turn is also a Mersenne prime equal to 127; and M₁₂₇ is in fact also a Mersenne prime, albeit one of 39 digits.

I wonder whether it's known whether there can be such chains of Mersenne primes of indefinite length (I don't know even if there are an infinitude of Mersenne primes in the first place, actually).

I really wish I knew of an intuitive argument which addressed and explained the apparent fact that it's very easy to ask seemingly simple questions about primes which are very hard to answer.
posted by jamjam at 4:54 PM on February 7

How does one test whether a given number is prime? Automated exhaustion testing?
posted by kafziel at 4:56 PM on February 7

damn son i'm so slick with the ladies that i got more digits than the recently discovered largest known prime
posted by cortex at 4:59 PM on February 7 [14 favorites]

Optimus lives!
posted by Sparx at 4:59 PM on February 7

damn son i'm so slick with the ladies that i got more digits than the recently discovered largest known prime
posted by cortex Fresh

Even Recent Activity sees you for what you are, cortex.
posted by Lemurrhea at 5:02 PM on February 7 [2 favorites]

For Mersenne primes, the Lucas-Lehmer test. In general there are a lot of ways, including one that runs in polynomial time, but they're all slow for very large numbers.
posted by madcaptenor at 5:05 PM on February 7

If you need a laugh you should read the Fox News article, which originally left out the minus-one and has gems like this:

Though there is little mathematical value to finding a single new prime, these rare numbers are prized in their own right by some.

I honestly find the tone of the article very... belittling.
posted by 23 at 5:05 PM on February 7 [1 favorite]

How does one test whether a given number is prime? Automated exhaustion testing?

One uses the Lucas–Lehmer primality test. To quote from the announcement:

To prove there were no errors in the prime discovery process, the new prime was independently verified using different programs running on different hardware. Serge Batalov ran Ernst Mayer's MLucas software on a 32-core server in 6 days (resource donated by Novartis IT group) to verify the new prime. Jerry Hallett verified the prime using the CUDALucas software running on a NVidia GPU in 3.6 days. Finally, Dr. Jeff Gilchrist verified the find using the GIMPS software on an Intel i7 CPU in 4.5 days and the CUDALucas program on a NVidia GTX 560 Ti in 7.7 days.

posted by Rhomboid at 5:07 PM on February 7

if 80085 appears somewhere in the decimal expansion

It's in there twice.
posted by DarkForest at 5:11 PM on February 7 [6 favorites]

If you need a laugh you should read the Fox News article, which originally left out the minus-one and has gems like this:

Oh, you don't know the half of it -- that article was originally posted with the sentence "Prime numbers, which are divisible only by themselves and one, have little mathematical importance," which was changed to the version you quoted after the inevitable derisive explosion of the mathematical tweetosphere.
posted by escabeche at 5:12 PM on February 7 [5 favorites]

Another interesting bit is the relation between Mersenne primes and (even) perfect numbers. Every Mersenne prime 2^p-1 corresponds to the perfect number 2^p-1(2^p-1), so the perfect number 2^57885160(2^57885161-1) was discovered, also only the 48th known and the largest.
posted by Rhomboid at 5:14 PM on February 7 [1 favorite]

Oops, got that wrong. It's in there at least 172 times...
posted by DarkForest at 5:22 PM on February 7

Also prime: 124739. Coincidence, intended by the poster, or act of Mod?
posted by Jon Mitchell at 5:25 PM on February 7 [11 favorites]

"Prime numbers, which are divisible only by themselves and one, have little mathematical importance"

Is that really what was on there originally? Like someone at Fox News just made that fact up out of whole cloth? I'm not being rhetorical, I'm obviously familiar with Fox News... it's just funny that with their size, they can't even find a science reporter (or mathematics specialist no less) that can write basic articles about news. Or maybe that's just their culture: "let's belittle something that is far removed from our world, and we don't understand it, because it plays to our stupid base."
posted by gagglezoomer at 5:31 PM on February 7 [1 favorite]

I love prime numbers. I use them when heating stuff in the microwave (e.g. instead of 30 seconds I'll tap in 31 seconds, 61 seconds instead of 1 minute, etc.). I don't think I'll be heating up anything for 2^ 57885161-1 seconds, though ...
posted by research monkey at 5:49 PM on February 7 [1 favorite]

Is that really what was on there originally?

Yes. Much hiliarity about it in math circles. But I think all that happened is they took a statement from somewhere that said "Finding a new prime number is not in itself so important" and failed to make the distinction between "finding a new prime number" and "prime numbers," which, to be fair, is somewhat subtle if it's a subject you've never thought about.

So I feel sort of bad for making fun of them on Twitter.

But not that bad.
posted by escabeche at 5:52 PM on February 7 [2 favorites]

(I don't know even if there are an infinitude of Mersenne primes in the first place, actually)

If it makes you feel better, you have this in common with every other human being on Earth.
posted by escabeche at 5:54 PM on February 7 [10 favorites]

is it 3?
posted by sexyrobot at 6:04 PM on February 7

Similarly to every time on Metafilter when a post is made about a newly-found or recently resurrected species, I am very comforted by the news of this wondrous new number.

I feel warmer inside knowing that there is a spot in our universe occupied by this number.
posted by Lipstick Thespian at 6:07 PM on February 7

- (2^57885161 - 1) + 17. This may not be prime, but 17 is pretty dodgy and it'll take them long enough to refute that it'll buy us some good glory time.

Um... it's even.

Right? I'm seriously worried I'm about to make a fool of myself.
posted by hoyland at 6:52 PM on February 7 [10 favorites]

Yes, trivially:

2^57885161 - 1 + 17 = 2^57885161 + 16 = 2(2^57885160 + 8), and all numbers n of the form n = 2k for some integer k are even.
posted by invitapriore at 6:59 PM on February 7 [5 favorites]

- (2^57885161 - 1) + 17. This may not be prime, but 17 is pretty dodgy and it'll take them long enough to refute that it'll buy us some good glory time.
Um... it's even.

It has been a while since I did any mathematics, but as I recall the multiples of 2 start to peter out around 12 billion . Once you get to 10⁶⁰ or so there are no even numbers at all.

(Jimmythefish, it was a close call but I think I deflected their suspicions)
posted by AndrewStephens at 7:05 PM on February 7 [15 favorites]

How does one test whether a given number is prime? Automated exhaustion testing?

The numbers involved are way, way too big for that.

To put this in perspective: right now, the fastest supercomputer on record is the Cray Titan. It will run a big shy of 18 petaflops, or 18 10^12 floating point operations per second.

Rounding up, there's a approximately 10^80 atoms in the observable universe. The estimated age of the universe according to wikipedia is about 4.4 * 10^18 seconds.

So, let's say for argument's sake that every single atom in the visible universe - every single piece of atomic matter within reach of our best space-borne telescopes - was a computer as powerful very best supercomputer we have ever built.

Rounding up again, that comes to about 80 * 10^110. A pretty big number, but still less than a hundred digits long.

The number in question is 17 _million_ digits long. We don't have prefixes to describe numbers that big, not by a long way. How much bigger is a thousand than one? How much bigger is a million than a thousand?

Now, try and imagine that difference happening over and over again almost six million times. That's how large this number is, even if every atom in the universe is the best supercomputer we know how to build, trying to take it apart.
posted by mhoye at 7:08 PM on February 7 [1 favorite]

Yes, trivially:

Trust me, the day I've been having mathematically, I have reason to doubt myself when I think 17-1=16.
posted by hoyland at 7:27 PM on February 7 [2 favorites]

"Yes, trivially" -- the mathematician's version of "Here, diagonally."
posted by escabeche at 7:46 PM on February 7 [1 favorite]

Oddly enough, I think we can also say:

"Yes, diagonally" -- the mathematician's version of "Here, trivially."

This prime seems too small, it's time to get infinite.
posted by Lemurrhea at 8:03 PM on February 7 [1 favorite]

Ha, to be clear I didn't mean that in the sense of "yes and you're an idiot for not being sure," but more in the sense of "yeah, and in answering this I am not trying to set myself up as some sort of genius," if that makes any sense.
posted by invitapriore at 8:07 PM on February 7 [1 favorite]

(Euclid chuckles.)
posted by Flunkie at 8:07 PM on February 7

The numbers involved are way, way too big for that.

No they're not. Exhaustive searching is exactly what the GIMPS project is doing, and has been doing for the last 17 years. You can view the status here. You can see that most of the currently assigned work units are for doing Lucas-Lehmer testing of exponents in the range of 50,000,000 - 61,000,000, so it's no surprise that the most recent find was 57,885,161. There's also a number of assigned work units for LL double checking of the previous results centered around the 30,000,000 range.
posted by Rhomboid at 8:10 PM on February 7

I think the question mhoye was responding to was how they do the primality testing for the candidates -- whether they exhaustively test possible divisors. To which the answer is indeed no, the numbers are way, way too big for that.
posted by escabeche at 8:16 PM on February 7

It is indeed massive, more than 17 million digits long. A text file of the entire number contains more than 22 megabytes of information.

I can't hope to top the brilliant jokes above - thanks for the first literal LOL of the day - but, wouldn't this seem like a truly bizarre choice to use even if it made sense? (True, I have opened 17 MB text files - but, only when I'm being exceptionally stupid and or lazy about moving data around. I rarely read them cover to cover.)

I don't know whether to be slightly excited that newspapers assume the average person has an instinct for how much data is in a MB of text, or slightly annoyed that so many other more physical examples were passed by. Surely "218,000 (80 character) lines" or "5400 (3200 char) pages" or a "27cm high stack of double-sided printed pages" would mean more to just about everyone?

Here's hoping it leads to even weirder choices in the future:

"If played as CD-quality stereo audio, it would take 41s to listen to the number."

"If each bit were represented by the placement of a suger cube, eating this number would supply the average American's energy needs for 5 years"

"If you wrote out each digit on a sandwich board and asked people to wear them, you'd need slightly more than the entire population of Chile. If they all stood shoulder to shoulder, they could line the route from Arica to Puerto Montt 5 people deep"

But, all these examples rely on someone already having an intuition for how exponentiation corresponds to the size of the number itself to recognize how large and precise it is. How about:

"If you wrote down the number in base-'number of atoms in the observable universe', you'd still need 4 digits."
posted by eotvos at 8:21 PM on February 7 [14 favorites]

escabeche: ""Yes, trivially" -- the mathematician's version of "Here, diagonally.""

Pretty sneaky, sis!
posted by Chrysostom at 9:01 PM on February 7

I'm taking an abstract math course this semester. That class and this conversation both make me realize I know nothing about math.
posted by MaritaCov at 9:09 PM on February 7

A text file of the entire number contains more than 22 megabytes of information.

They probably just pasted the entire thing into a Word document.
posted by Dr Dracator at 9:13 PM on February 7

I'm taking an abstract math course this semester. That class and this conversation both make me realize I know nothing about math.

I have a degree in math and some of this stuff makes me think I don't know much about math. But, to be fair, this is number theory, which is just plain difficult, in my opinion. I suppose it doesn't help that the course I took on it for my degree met at 8:30am (which, ye gods, I've hardly had any coffee yet), but you can take some comfort that Gauss called number theory the queen of mathematics, so, y'know, it's not like the court jester is kicking your ass here.
posted by axiom at 9:15 PM on February 7 [4 favorites]

I don't know who Elizabeth Landau is, but I think I might love her.

I have little substantive to say on this topic, other than that Liz Landau is a good friend of mine from undergrad and it's awesome that she's made MetaFilter. I know she was thrilled to get to write this particular article. I have never known anyone else to celebrate Pi Day with such reverence and glee.
posted by ilana at 9:26 PM on February 7 [1 favorite]

Yeah, I don't know what it is about number theory, maybe it's that the objects under consideration seem irreducable in a way that makes them more difficult to reason about. I just know that when I think about e.g. open problems in graph theory or something my brain goes, oh, cool, maybe if you... But when I think about something like the 3n + 1 conjecture my brain goes, nope, not happening, let's get a sandwich.
posted by invitapriore at 9:38 PM on February 7 [2 favorites]

Out of interest how long does it take a computer to check whether this huge number is a prime or not? Could we not somehow use a system similar to folding@home to come up with more of these elusive little buggers?
posted by aqueousdan at 10:07 PM on February 7

Ok 39 days I see. We could get that down a bit if we all chipped in!
posted by aqueousdan at 10:11 PM on February 7

We could! You want the Great Internet Mersenne Primes Search (GIMPS), which is the very effort that found this prime.
posted by LobsterMitten at 10:13 PM on February 7

One has to wonder about the magic of a universe that has somehow managed to sort itself out in such a way that such mathematics are possible, where prime numbers not only exist but are the atoms of a natural, countable world.
posted by Blazecock Pileon at 11:03 PM on February 7

gagglezoomer: Is it generally accepted among mathematics experts that no one will ever find a formula for predicting prime numbers?

Not even vaguely a mathematician, but I believe that is not accepted at all. There seems to be a general sense that a pattern to primality does exist, but that nobody has figured out what it is yet.

Here's a link that talks about the subject a little bit: New Pattern Found in Prime Numbers.

The thought occurs, suddenly, that if anyone does find the pattern for prime numbers, it would be worth an enormous amount of money if kept secret.
posted by Malor at 11:10 PM on February 7

If you just want a prime number and don't care about any other properties like knowing that it's the nth prime can't you just generate them by multiplying together all the integers from 1 up to some large n and then adding or subtracting 1? What am I missing?
posted by tomcooke at 11:37 PM on February 7

Malor, if such a pattern were known it would probably make it much easier to break any encryption scheme using prime numbers, e.g. RSA. If anyone knows about a pattern like that it would probably be the NSA, which has very smart people indeed and practically limitless funds for research. The NSA is notoriously close-mouthed, but they stepped in to improve the security of DES when the public version had a weakness that wasn't publicly known. I think (I hope) that if they knew of the existence of a pattern like this they'd publicise it, or at least get people to stop using public key encryption.
posted by Joe in Australia at 11:38 PM on February 7

I think it's safe to assume that after the election, Fox News hasn't exactly been on good terms with math. They won't even return its phone calls.
posted by TheSecretDecoderRing at 12:21 AM on February 8 [1 favorite]

Is there a list somewhere of primes? All the ones I can find top out low, the highest I could find tops out at 100 trillion.
posted by kafziel at 12:24 AM on February 8

Tomcooke, that number isn't necessarily prime, it's just not divisible by any of the numbers you used. It could be composite, and divisible by some prime larger than n. For example, 8!-1 is 40319 = 23 * 1753.
posted by Elementary Penguin at 1:24 AM on February 8 [3 favorites]

"- (2^57885161 - 1) + 17. This may not be prime, but 17 is pretty dodgy and it'll take them long enough to refute that it'll buy us some good glory time."

Um... it's even.

Right? I'm seriously worried I'm about to make a fool of myself.

Sorry, but (2^57885161 - 1) + 17 is odd. Since (2^57885161 - 1) is even, being the second even prime discovered!

The first one, of course, being 2.

Almost as excitingly, (2^57885161 - 1) isn't just divisible by 2, (i.e. even), it's also divisible by 3! Primes divisible by 3 are very rare, and mathematicians get very excited when they discover them.

Mathematicians currently have no idea if they will discover any other even primes besides 2 and (2^57885161 - 1).
posted by sebastienbailard at 2:00 AM on February 8 [3 favorites]

Elementary Penguin, thanks for that explanation which seems obvious in retrospect!
posted by tomcooke at 4:52 AM on February 8

can't you just generate them by multiplying together all the integers from 1 up to some large n and then adding or subtracting 1? What am I missing?

That number won't be divisible by any integer between 1 and n, but it certainly might have divisors between n and its big old self.
posted by escabeche at 4:53 AM on February 8

Not even vaguely a mathematician, but I believe that is not accepted at all. There seems to be a general sense that a pattern to primality does exist, but that nobody has figured out what it is yet.

The prime numbers exhibit many statistical regularities, but that's a very different thing from a formula for producing primes rapidly, which I don't think is expected.

Malor, if such a pattern were known it would probably make it much easier to break any encryption scheme using prime numbers, e.g. RSA.

Not really; RSA rests on the difficulty of factoring large composite numbers, not finding large prime numbers. If you're trying to factor some large number N, it's not good enough to find primes; you have to find the ones which are divisors of N, a problem which appears to be substantially more difficult.
posted by escabeche at 5:47 AM on February 8 [3 favorites]

can't you just generate them by multiplying together all the integers from 1 up to some large n and then adding or subtracting 1? What am I missing?

(1)(2)(3)(4) + 1 = 25 = 5*5.
posted by madcaptenor at 11:51 AM on February 8 [1 favorite]

(1)(2)(3)(4) + 1 = 25 = 5*5.

I think tomcooke meant to multiply all of the primes up to some value and add one, not all of the integers. But this also doesn't work since, for example, 2*3*5*7*11*13*17*19 + 1 = 347*27953.
posted by klausman at 1:27 PM on February 8 [1 favorite]