2^82,589,933 − 1
December 22, 2018 6:32 AM Subscribe
The world has a new largest prime number! The number is known as a Mersenne prime and was discovered by a computer on December 7. Mathematicians have spent the past two weeks verifying the 24.8 million digit number.
There isn't a largest prime number - it has been proven. So, there cannot be a new largest one. QED.
posted by thelonius at 6:42 AM on December 22, 2018 [3 favorites]
posted by thelonius at 6:42 AM on December 22, 2018 [3 favorites]
Sorry, I guess it’s a largest-known prime.
posted by stillmoving at 6:51 AM on December 22, 2018 [4 favorites]
posted by stillmoving at 6:51 AM on December 22, 2018 [4 favorites]
It would only take you nine and half months to write it down, working 24/7 and averaging a second a digit.
posted by fearfulsymmetry at 6:59 AM on December 22, 2018 [1 favorite]
posted by fearfulsymmetry at 6:59 AM on December 22, 2018 [1 favorite]
Sorry, I guess it’s a largest-known prime.
was joke!
posted by thelonius at 7:07 AM on December 22, 2018 [1 favorite]
was joke!
posted by thelonius at 7:07 AM on December 22, 2018 [1 favorite]
Can we eat it?
No, by the time you finish verifying it, it has sat out too long. This is especially true for Mersenne Prime Rib.
posted by GenjiandProust at 7:22 AM on December 22, 2018 [30 favorites]
No, by the time you finish verifying it, it has sat out too long. This is especially true for Mersenne Prime Rib.
posted by GenjiandProust at 7:22 AM on December 22, 2018 [30 favorites]
Helen Arney’s thoughts about Christmas and Mersenne 48
posted by GenjiandProust at 7:30 AM on December 22, 2018
posted by GenjiandProust at 7:30 AM on December 22, 2018
The question I always have when news like this comes up is "how did you check?" so I finally went and looked it up, and the answer is kinda great.
There's no way to do this exhaustively, by checking all the possibilities one at a time. The numbers involved are so huge - 2^82,589,933 - 1 is something like 28 million digits long - that even if every atom in the universe had the computational capacity of all of AWS at once and ran full out from now to the heat death of the universe it wouldn't put a dent in a job that size.
But there's this neat property that prime numbers have, proved by Fermat's (that Fermat, like there's another one) Little Theorem, stating that for any prime p:
The neat things is that this holds for prime numbers - as in, if p is prime, that equation guaranteed to hold true for any positive integer a - but it may also be true for some combinations of a and p where p is a non-prime ("composite") number, and these are called "Charmichael numbers".
Charmichael numbers are pretty scarce around the normal-human-arithmetic-scale end of the integers. The smallest one is 561, and there's only seven of them less than 10,000. But once numbers start getting very big they start getting really rare; per the Wikipedia article there are 20,138,200 Carmichael numbers between 1 and 1021, which amounts to about one every 50 trillion or so.
The upshot of this, which I think is pretty great, is that even if you can't find prime numbers easily, it's (relatively) straightforward to test if something is likely to be prime and keep testing it until the amount of uncertainty involved is basically a grain of sand in the ocean of your hardware's error rate.
This is one of a few different probabilistic primality tests out there, and probably the easiest one to implement/explain, but the whole idea is pretty cool.
posted by mhoye at 7:51 AM on December 22, 2018 [37 favorites]
There's no way to do this exhaustively, by checking all the possibilities one at a time. The numbers involved are so huge - 2^82,589,933 - 1 is something like 28 million digits long - that even if every atom in the universe had the computational capacity of all of AWS at once and ran full out from now to the heat death of the universe it wouldn't put a dent in a job that size.
But there's this neat property that prime numbers have, proved by Fermat's (that Fermat, like there's another one) Little Theorem, stating that for any prime p:
ap = a (mod p)As one example of, um, infinitely many: 43 = 64 = 3*20 + 4 = 4 (mod 3)
The neat things is that this holds for prime numbers - as in, if p is prime, that equation guaranteed to hold true for any positive integer a - but it may also be true for some combinations of a and p where p is a non-prime ("composite") number, and these are called "Charmichael numbers".
Charmichael numbers are pretty scarce around the normal-human-arithmetic-scale end of the integers. The smallest one is 561, and there's only seven of them less than 10,000. But once numbers start getting very big they start getting really rare; per the Wikipedia article there are 20,138,200 Carmichael numbers between 1 and 1021, which amounts to about one every 50 trillion or so.
The upshot of this, which I think is pretty great, is that even if you can't find prime numbers easily, it's (relatively) straightforward to test if something is likely to be prime and keep testing it until the amount of uncertainty involved is basically a grain of sand in the ocean of your hardware's error rate.
This is one of a few different probabilistic primality tests out there, and probably the easiest one to implement/explain, but the whole idea is pretty cool.
posted by mhoye at 7:51 AM on December 22, 2018 [37 favorites]
Is anything known about what proportion of primes are Mersenne primes?
posted by Nancy Lebovitz at 8:12 AM on December 22, 2018
posted by Nancy Lebovitz at 8:12 AM on December 22, 2018
Good ol' GIMPS, it's been running strong 22 years now. Surely the world's longest lived cloud computation, if not also possibly the largest. Way back in the long ago I tried to make a business out of this kind of volunteer-cycle computing. It's a bad business for various reasons, but it's a good way to solve specific problems where people are enthusiastic but there's not a lot of money to pay for the CPU time.
I hope this prime was welcomed into the world better than 2^74,207,281 - 1 was. That one was found to be prime, reported to the GIMPS server, and then no one noticed until someone looked at a log file three months later. Oops.
posted by Nelson at 8:35 AM on December 22, 2018 [12 favorites]
I hope this prime was welcomed into the world better than 2^74,207,281 - 1 was. That one was found to be prime, reported to the GIMPS server, and then no one noticed until someone looked at a log file three months later. Oops.
posted by Nelson at 8:35 AM on December 22, 2018 [12 favorites]
Ugh spoiler in the title
posted by Pronoiac at 8:51 AM on December 22, 2018 [11 favorites]
posted by Pronoiac at 8:51 AM on December 22, 2018 [11 favorites]
mhoye, I don't think that's how GIMPS works. Mersenne numbers (numbers of the form 2n–1) are easier to deterministically test for primality than other numbers of comparable size, thanks to the Lucas-Lehmer test (intro / deeper explanation).
Sorry, I guess it’s a largest-known prime.
That's a funny place to put the hyphen! (Is also joke. Mainly I bring this up because it reminds me of a fun conversation I had with some students about the distinction between a "best known method" and a "best-known method"... a distinction which is also sometimes a difference.)
posted by aws17576 at 10:18 AM on December 22, 2018 [7 favorites]
Sorry, I guess it’s a largest-known prime.
That's a funny place to put the hyphen! (Is also joke. Mainly I bring this up because it reminds me of a fun conversation I had with some students about the distinction between a "best known method" and a "best-known method"... a distinction which is also sometimes a difference.)
posted by aws17576 at 10:18 AM on December 22, 2018 [7 favorites]
By the way, the Lucas-Lehmer test is why all the record primes have been Mersenne primes for a while. It's not that there aren't tons of other large primes, we just have no way to identify them.
posted by aws17576 at 10:21 AM on December 22, 2018 [6 favorites]
posted by aws17576 at 10:21 AM on December 22, 2018 [6 favorites]
> Is anything known about what proportion of primes are Mersenne primes?
Mersenne Primes are a vanishingly small percentage of the total number of primes.
Just for example, there are just 45 Mersenne Primes below 237,156,667.
Let's call p the total number of primes below that same number (237,156,667) .
Thanks to the Prime Number Theorem, p is actually rather easy to calculate. It is a very large number--approximately 11,185,247 digits.
To a reasonable approximation then, the proportion of Mersenne Primes to Primes is 45/1011,185,247.
So the you've got 1 Mersenne Prime for about every 1011,185,245 regular primes.
That's not very many!
posted by flug at 10:31 AM on December 22, 2018 [9 favorites]
Mersenne Primes are a vanishingly small percentage of the total number of primes.
Just for example, there are just 45 Mersenne Primes below 237,156,667.
Let's call p the total number of primes below that same number (237,156,667) .
Thanks to the Prime Number Theorem, p is actually rather easy to calculate. It is a very large number--approximately 11,185,247 digits.
To a reasonable approximation then, the proportion of Mersenne Primes to Primes is 45/1011,185,247.
So the you've got 1 Mersenne Prime for about every 1011,185,245 regular primes.
That's not very many!
posted by flug at 10:31 AM on December 22, 2018 [9 favorites]
Is anything known about what proportion of primes are Mersenne primes?
To add to what flug said, while Mersenne primes are definitely at most a tiny proportion of all primes, we don't know if there are infinitely many Mersenne primes. (There are infinitely many primes.) It's always possible that the last Mersenne prime found by GIMPS is, truly, the last Mersenne prime. But mathematicians don't think that's very likely.
The reason is that we have a way of guessing how likely a number is to be prime, given its size. Among the numbers 1 to N, the proportion of primes is approximately 1/(log N), where the logarithms are natural logarithms. This is the content of the Prime Number Theorem mentioned above. Although it's an estimate, the theorem actually says something that's provable: as N goes to infinity, the relative error of the estimate goes to 0.
The Prime Number Theorem can be glossed as "The probability of a randomly chosen number up to N being prime is about 1/(log N)". As N goes to infinity, this probability drops very, very slowly -- so slowly that if we had a totally random sequence of integers that grow at the same rate as the Mersenne numbers, it would be almost certain that that sequence would contain infinitely many primes.
But you can see the problem with this reasoning: Mersenne numbers aren't "totally random". What if they are biased toward not being prime? In fact, they are: 2n–1 cannot be prime unless n is prime as well, because any factorization of n can be used to factor 2n–1. Nevertheless, even when this bias is taken into account, there should be infinitely many Mersenne primes unless there is some other bias we don't know about. This is basically the status of a lot of hypotheses about the prime numbers. We see order at the zoomed-out level of "all primes up to N", and we can prove it. We see randomness at the zoomed-in level of the individual prime, but we can't prove it. So we make guesses based on the statistical properties of random numbers, but we can't be sure there isn't a hidden conspiracy among the primes to falsify those guesses.
posted by aws17576 at 10:57 AM on December 22, 2018 [13 favorites]
To add to what flug said, while Mersenne primes are definitely at most a tiny proportion of all primes, we don't know if there are infinitely many Mersenne primes. (There are infinitely many primes.) It's always possible that the last Mersenne prime found by GIMPS is, truly, the last Mersenne prime. But mathematicians don't think that's very likely.
The reason is that we have a way of guessing how likely a number is to be prime, given its size. Among the numbers 1 to N, the proportion of primes is approximately 1/(log N), where the logarithms are natural logarithms. This is the content of the Prime Number Theorem mentioned above. Although it's an estimate, the theorem actually says something that's provable: as N goes to infinity, the relative error of the estimate goes to 0.
The Prime Number Theorem can be glossed as "The probability of a randomly chosen number up to N being prime is about 1/(log N)". As N goes to infinity, this probability drops very, very slowly -- so slowly that if we had a totally random sequence of integers that grow at the same rate as the Mersenne numbers, it would be almost certain that that sequence would contain infinitely many primes.
But you can see the problem with this reasoning: Mersenne numbers aren't "totally random". What if they are biased toward not being prime? In fact, they are: 2n–1 cannot be prime unless n is prime as well, because any factorization of n can be used to factor 2n–1. Nevertheless, even when this bias is taken into account, there should be infinitely many Mersenne primes unless there is some other bias we don't know about. This is basically the status of a lot of hypotheses about the prime numbers. We see order at the zoomed-out level of "all primes up to N", and we can prove it. We see randomness at the zoomed-in level of the individual prime, but we can't prove it. So we make guesses based on the statistical properties of random numbers, but we can't be sure there isn't a hidden conspiracy among the primes to falsify those guesses.
posted by aws17576 at 10:57 AM on December 22, 2018 [13 favorites]
Thank you, mhoye, for that very helpful comment on Fermat’s other theorem. I’d never heard of the “mod” term in math, but just now finished reading up on it. It solves a little personal mathematical conundrum related to the Fibonacci series I’ve idly been musing on for over 30 years. Very happy to have closure on that thought experiment!
posted by darkstar at 11:32 AM on December 22, 2018 [3 favorites]
posted by darkstar at 11:32 AM on December 22, 2018 [3 favorites]
And I thought the largest possible prime was Amazon Prime.
posted by oneswellfoop at 11:41 AM on December 22, 2018 [4 favorites]
posted by oneswellfoop at 11:41 AM on December 22, 2018 [4 favorites]
...was discovered by a computer on December 7.
At last my birthday will be known for something other than Pearl Harbor!
posted by TedW at 2:04 PM on December 22, 2018 [2 favorites]
At last my birthday will be known for something other than Pearl Harbor!
posted by TedW at 2:04 PM on December 22, 2018 [2 favorites]
I recently thought one of the major errors in cryptocurrency was tying mining to random calculations instead of using it for something like this.
posted by solarion at 2:34 PM on December 22, 2018 [1 favorite]
posted by solarion at 2:34 PM on December 22, 2018 [1 favorite]
For anyone who heats with electricity ... and has a spare reasonably fast computer sitting around ... this is *the* time of the year to run a test of a Mersienne-prime candidate.
Before the electricity becomes heat, it's applied to that problem. (Imagine if *everyone* electric did this!) Now, mind you, your candidate will, most probably, eventually fail to be prime. And you might need a couple of months to find that out.
OTOH, IF you DO find a prime, you get momentarily famous! And your name becomes part of the Permanent Record!
posted by Twang at 2:36 PM on December 22, 2018 [1 favorite]
Before the electricity becomes heat, it's applied to that problem. (Imagine if *everyone* electric did this!) Now, mind you, your candidate will, most probably, eventually fail to be prime. And you might need a couple of months to find that out.
OTOH, IF you DO find a prime, you get momentarily famous! And your name becomes part of the Permanent Record!
posted by Twang at 2:36 PM on December 22, 2018 [1 favorite]
ap = a (mod p)I hate to be doing this, but I can't let this one mistake (or nit) pass by in an otherwise wonderfully informative comment. It's not possible for anything to be equal to 4 (mod 3). Something can be congruent to 4, but not equal.
As one example of, um, infinitely many: 43 = 64 = 3*20 + 4 = 4 (mod 3)
It's ap (mod p) = a (mod p) or ap ≡ a (mod p). [fancy three-bar equals is congruence]
thank you. i'm sorry. thank you
posted by cardioid at 3:12 PM on December 22, 2018 [10 favorites]
Also, to give a useful comment and not just crap on someone else's, I really enjoyed learning about this and related things from Arthur Benjamin's video lectures on discrete mathematics, available from Great Courses.
posted by cardioid at 3:17 PM on December 22, 2018 [1 favorite]
posted by cardioid at 3:17 PM on December 22, 2018 [1 favorite]
My library card number!
posted by Armed Only With Hubris at 4:31 PM on December 22, 2018 [4 favorites]
posted by Armed Only With Hubris at 4:31 PM on December 22, 2018 [4 favorites]
I hate to be doing this, but I can't let this one mistake (or nit) pass by in an otherwise wonderfully informative comment.
Ugh, what a mess. You're correct, of course, and that is an obvious error I should have caught. Thank you for calling it out.
posted by mhoye at 7:06 PM on December 22, 2018
Ugh, what a mess. You're correct, of course, and that is an obvious error I should have caught. Thank you for calling it out.
posted by mhoye at 7:06 PM on December 22, 2018
So, can someone explain in layman's terms the value of finding larger and larger primes?
posted by praemunire at 9:54 PM on December 22, 2018 [1 favorite]
posted by praemunire at 9:54 PM on December 22, 2018 [1 favorite]
I don't think "value" is precisely the relevant characteristic.
posted by clockzero at 11:38 PM on December 22, 2018 [5 favorites]
posted by clockzero at 11:38 PM on December 22, 2018 [5 favorites]
Ugh, what a mess. You're correct, of course, and that is an obvious error I should have caught. Thank you for calling it out.
While we're being Christmas pedants, it's Carmichael Number, not Charmichael, which I assume is a Pokemon. We still <3 you, mhoye.
posted by axiom at 12:09 AM on December 23, 2018 [1 favorite]
While we're being Christmas pedants, it's Carmichael Number, not Charmichael, which I assume is a Pokemon. We still <3 you, mhoye.
posted by axiom at 12:09 AM on December 23, 2018 [1 favorite]
the proportion of Mersenne Primes to Primes is 45/10^11,185,247.
This is only true if we're sure there are only 45 Mersenne primes < 10^11,185,247. But GIMPS isn't quite that thorough. The web page says "All exponents below 46 118 053 have been tested and verified. All exponents below 81 835 723 have been tested at least once." So we can say something pretty definitive up to 2^46,118,053 (including your 45) but not beyond. There's some further notes on the importance of "verification" on the site (see April 2 2018 update). Sometimes they are found out of order.
There's a second philosophical problem; these tests are physical computations. Something might have gone wrong with the computer. If I understand the math correctly, a proof that a number is prime is easy enough to verify that there's no doubt once one is established. But proving it is not prime is so expensive it's only been done once or twice for many candidates. There's still a probability the computation failed and yielded a non-true result. I wonder what their verification algorithm is; are they just running the tests a second time, or are they doing something more explicit that generates a verifiable proof?
But what I'm really curious about... does (# Mersennes < N) / (# Primes < N) go to 0 as N goes to infinity? Or does it converge at some > 0 number? The prime number theory tells us that (# Primes < N) / N > 0, right?
posted by Nelson at 12:43 AM on December 23, 2018
This is only true if we're sure there are only 45 Mersenne primes < 10^11,185,247. But GIMPS isn't quite that thorough. The web page says "All exponents below 46 118 053 have been tested and verified. All exponents below 81 835 723 have been tested at least once." So we can say something pretty definitive up to 2^46,118,053 (including your 45) but not beyond. There's some further notes on the importance of "verification" on the site (see April 2 2018 update). Sometimes they are found out of order.
There's a second philosophical problem; these tests are physical computations. Something might have gone wrong with the computer. If I understand the math correctly, a proof that a number is prime is easy enough to verify that there's no doubt once one is established. But proving it is not prime is so expensive it's only been done once or twice for many candidates. There's still a probability the computation failed and yielded a non-true result. I wonder what their verification algorithm is; are they just running the tests a second time, or are they doing something more explicit that generates a verifiable proof?
But what I'm really curious about... does (# Mersennes < N) / (# Primes < N) go to 0 as N goes to infinity? Or does it converge at some > 0 number? The prime number theory tells us that (# Primes < N) / N > 0, right?
posted by Nelson at 12:43 AM on December 23, 2018
FYI: the zip file offered by NPR downloads 11.6 megabytes (MB), in case you had any concerns with what NPR calls "gigantic" filling your storage.
posted by filtergik at 5:17 AM on December 23, 2018
posted by filtergik at 5:17 AM on December 23, 2018
Oh, and that zip file expands to 25.4 megabytes (MB) text file containing the number itself.
posted by filtergik at 5:22 AM on December 23, 2018 [3 favorites]
posted by filtergik at 5:22 AM on December 23, 2018 [3 favorites]
Interestingly, this prime number, like most prime numbers, is odd. In fact mathematicians are still only aware of one even prime number!
posted by Joe in Australia at 10:33 AM on December 23, 2018 [2 favorites]
posted by Joe in Australia at 10:33 AM on December 23, 2018 [2 favorites]
The prime number theory tells us that (# Primes < N) / N > 0, right?
No, I don't think that's true. π(x) = x/ln(x) for large values of x, so:
(# Primes < N) / N = π(x)/x = (x/ln(x))/x = 1/ln(x) → 0
posted by axiom at 12:28 PM on December 23, 2018 [1 favorite]
No, I don't think that's true. π(x) = x/ln(x) for large values of x, so:
(# Primes < N) / N = π(x)/x = (x/ln(x))/x = 1/ln(x) → 0
posted by axiom at 12:28 PM on December 23, 2018 [1 favorite]
any factorization of n can be used to factor 2n–1.
can anyone point me to a proof of this?
posted by thelonius at 12:56 PM on December 23, 2018 [1 favorite]
can anyone point me to a proof of this?
posted by thelonius at 12:56 PM on December 23, 2018 [1 favorite]
can anyone point me to a proof of this?
I haven't worked out an entire proof but the crux seems to be to use the geometric series expansion:
xn - 1 = (x - 1)(1 + x + x2 + ··· +xn-1)
If we know that our n = ab (where a and b may themselves be products of primes), we can substitute x = (2a) and n = b in the above, yielding:
2n - 1 = (2a - 1)(1 + 2a + 22a + ··· + (2a)b-1)
So clearly both 2a - 1 and 2b - 1 are factors of 2n-1.
posted by axiom at 7:37 PM on December 23, 2018 [1 favorite]
I haven't worked out an entire proof but the crux seems to be to use the geometric series expansion:
xn - 1 = (x - 1)(1 + x + x2 + ··· +xn-1)
If we know that our n = ab (where a and b may themselves be products of primes), we can substitute x = (2a) and n = b in the above, yielding:
2n - 1 = (2a - 1)(1 + 2a + 22a + ··· + (2a)b-1)
So clearly both 2a - 1 and 2b - 1 are factors of 2n-1.
posted by axiom at 7:37 PM on December 23, 2018 [1 favorite]
So, can someone explain in layman's terms the value of finding larger and larger primes?
It's aesthetic. Some people enjoy the pleasure of knowing large prime numbers, and some of them enjoy it enough to write software to find them or devote spare CPU cycles to it. Some of the technologies and algorithms developed along the way may turn out to have use in other applications, but that's incidental.
posted by biogeo at 7:42 PM on December 23, 2018 [1 favorite]
It's aesthetic. Some people enjoy the pleasure of knowing large prime numbers, and some of them enjoy it enough to write software to find them or devote spare CPU cycles to it. Some of the technologies and algorithms developed along the way may turn out to have use in other applications, but that's incidental.
posted by biogeo at 7:42 PM on December 23, 2018 [1 favorite]
I'm sort of into information theory (security/crypto does that), and one way of thinking of prime numbers is that they're the output of programs we aren't amazing at characterizing. Like, we are pawing around what the programs do, but we're missing something.
Suppose you're enumerating all primes sequentilally. You get to two, and now you remember you have to remove all even numbers -- 4, 6, 8, 10, etc. Now you get to 3, and you have to remove all multiples of 3 -- 6, 9, 12. You remember you removed 4, you never got around to removing 5, so 5 stays. But you remember now you must remove 10, 15, 20, 25, 30.
It's a program where you have to remember more and more. But we can talk about very large primes without having remembered anything. Somehow that accumulated knowledge is compressible.
Recognizing the properties of programs we haven't, and couldn't entirely enumerate -- that's not just something we want to do for prime numbers. That's computer security itself.
posted by effugas at 7:11 PM on December 24, 2018
Suppose you're enumerating all primes sequentilally. You get to two, and now you remember you have to remove all even numbers -- 4, 6, 8, 10, etc. Now you get to 3, and you have to remove all multiples of 3 -- 6, 9, 12. You remember you removed 4, you never got around to removing 5, so 5 stays. But you remember now you must remove 10, 15, 20, 25, 30.
It's a program where you have to remember more and more. But we can talk about very large primes without having remembered anything. Somehow that accumulated knowledge is compressible.
Recognizing the properties of programs we haven't, and couldn't entirely enumerate -- that's not just something we want to do for prime numbers. That's computer security itself.
posted by effugas at 7:11 PM on December 24, 2018
Arthur Benjamin's video lectures on discrete mathematics, available from Great Courses
I watched this entire course a year ago and, yes, it's great.
posted by neuron at 9:22 AM on December 25, 2018
I watched this entire course a year ago and, yes, it's great.
posted by neuron at 9:22 AM on December 25, 2018
« Older It’s not just a meat snack, It’s a way of life! | “My Spanish isn’t very good, but I could see it... Newer »
This thread has been archived and is closed to new comments
posted by radwolf76 at 6:40 AM on December 22, 2018 [27 favorites]