8 ms·
The largest known prime number has emerged. It has more than 23M digits
- TekMol 9y agoI have two questions: 1: How do we know it's the largest known prime number? What qualifies as a 'known' prime number? Is there an official registry somewhere? 2: Are all prime numbers smaller then this one also known? Or could somebody still come up with an unknown 'not very large prime number'?
- Ohmycosh 9y agohttps://www.mersenne.org/primes/ https://www.mersenne.org/primes/ For Mersennes at least, which right now are the largest primes. A prime is known once you've shown it is prime, i.e. no factors other than 1 and itself.
- colbyh 9y ago1. Essentially, yes there's a list. Since there doesn't exist a higher level formula to identify primes it's been verified by some variation of a brute force method. 2. That all smaller primes are known can't be verified. Primes of this size are usually found by a number of formulas that find "likely" primes and then verified by brute force (afaik). Because of that fuzzy match to start there might be smaller primes that haven't yet been identified.
- planteen 9y agoCalling it brute force isn't quite right. There is an efficient algorithm for prime determination (Lucas-Lehmer primality test) on Mersenne Primes (numbers of the form 2^p-1). https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test
- colbyh 9y agoThanks for the reminder! And this is my bad because I was paywalled on my phone and didn't see that it was, in fact, a mersenne prime that was found.
- Someone 9y agoWe know for sure that we don’t know all smaller primes. For example, there is at least one prime between 2^77,232,915 and 2^77,232,916 that we don’t know (https://en.wikipedia.org/wiki/Bertrand%27s_postulate https://en.wikipedia.org/wiki/Bertrand%27s_postulate) (That’s a very loose bound. I think that, for any N > 2, there are more primes than squares of integers less than it)
- throwacide 9y agoWhat’s the significance of primes being one less than large powers of 2? Does this mean base-2 is the most natural base?
- Someone 9y ago2 is the only integer n such that n-1 = 1. That’s significant because (n^m) - 1 is divisible by n - 1. So, for example, 125320078^35785332 - 1 is divisible by 125320077 and, hence, not a prime. So, this problem has been solved for all n>2. n^m + 1 is a more difficult problem. For example, for n=10, we get 2: prime, 11: prime, 101: prime, 1001: composite, 10001: composite, etc (at least the 8,000 following are composite. See https://math.stackexchange.com/questions/2108085/is-there-a-prime-which-is-the-form-of-10n-1-except-2-11-101 https://math.stackexchange.com/questions/2108085/is-there-a-...)
- throwacide 9y agoOh, neat. Thanks.
- pronoiac 9y ago1. Mersenne numbers (of the form 2^n - 1) are far easier to prove primality than other similarly sized numbers. It looks like there is a registry! Details for adding an item are at https://primes.utm.edu/notes/faq/add_prime.html https://primes.utm.edu/notes/faq/add_prime.html 2. We haven't enumerated the vast majority of the primes under this. There could even be mersenne primes as yet unexamined smaller than this, as the search is distributed. And whenever an ssl certificate is generated, two (hopefully) previously undiscovered prime numbers is found. (For 1024-bit length keys, that's around 308 digits.) The magnitude of the numbers involved is hard to think about. The number of protons in the observable universe "only" has around 80 digits. References: * Mersenne primes - https://en.wikipedia.org/wiki/Mersenne_prime https://en.wikipedia.org/wiki/Mersenne_prime * Eddington number -https://en.wikipedia.org/wiki/Eddington_number https://en.wikipedia.org/wiki/Eddington_number
- pronoiac 9y agoHere's a page on the distribution of prime numbers. http://primes.utm.edu/howmany.html http://primes.utm.edu/howmany.html I tried to estimate how many prime numbers there were below this number, and Wolfram Alpha timed out, though I got the density estimated, I think.[1] If I remember my logarithm math, around one in 50 million numbers at this magnitude is prime, but that's still gigantic! The count of prime numbers smaller than this prime number is also around 23 million digits long. [1] http://m.wolframalpha.com/input/?i=%28log+2%29+*+77%2C232%2C917 http://m.wolframalpha.com/input/?i=%28log+2%29+*+77%2C232%2C...
- tzs 9y ago> Are all prime numbers smaller then this one also known? No, and they will never all be known. There are approximately n/log(n) primes less than n. In this case n is 2^77232917 - 1. n/log(n) is approximately 8.6 x 10^2317930. If you gave every person on Earth a million million processors [1], running at 1000 GHz each, that could find a prime each clock cycle, and each person used a time machine to send their processors back to when the dinosaurs went extinct so they by now they have all been running 65 million years...we'd have found about 1.4 x 10^49 primes. Heck, if every particle in the universe was somehow made to computer, each of which could produce a new prime in the time it takes light to travel the Planck length (the smallest meaningful length possible in the universe), and they had all been doing this since the beginning of the universe, they would have discovered by now about 10^147 primes. That's a mere 0.000...00012 percent of the way there, where I've skipped more than 23000000 zeros.
- SurrealSoul 9y ago>"Anyone can download the software free. So you, too, could discover a record-breaking prime number — if you have enough patience." Maybe mining zcash is lucrative, but finding a new big prime number sounds pretty nice
- eternalcode 9y agoI wish we can collectively "mine" solutions for questions that are currently un-solved. Like Larger prime number, or create a hive mind that acts as an AI.
- SketchySeaBeast 9y agoIsn't that the point of projects like folding@home? And hive mind AI is literally skynet.
- pavel_lishin 9y agoThe Borg would be a better analogy; Skynet was just an AI with a specific purpose, no hive-mind about it.
- SketchySeaBeast 9y agoWell that's more reassuring.
- sweeneyrod 9y agoThere are attempts to do this, for instance Primecoin and Curecoin.
- cnvogel 9y agoQuote from the Article: """The figure is calculated by multiplying 2 by itself 77,232,917 times and then subtracting 1.""" Would HN agree that multiplying 2 by itself once is 2⨯2 = pow(2,2), twice is 2⨯2⨯2 = pow(2,3) and N times yields pow(2,N+1)? The Mersenne Prime found is pow(2,77232917) − 1, hence the article got the number wrong?
- mattashii 9y agoIf you're going that way, you can also interpret it - pardon my programming - as the following: int result; for (int i = 0; i < 77232917; i++) { result = 2 * 2; } return result - 1; ... which obviously results in 3. Also a (mersienne) prime, but not quite as big as you'd expect, and certainly not millions of digits long.
- deleted 9y ago[deleted]
- teilo 9y agoYeah, I suppose if one wants to be pedantic. But we know what it means.
- nopacience 9y agoint result; for (int i = 0; i < 77232917; i++) { result = 2 * 2; <----- you basically said result=4 77232917 times } return result - 1; <--- and then 4-1=3 so of course it will always be 3
- colanderman 9y agoThat is the joke.
- pavel_lishin 9y agoDang ol' off-by-one errors.
- auggierose 9y agoGiven that we know that there are infinitely many primes, why are we interested in knowing ever larger ones? It's somewhat like asking, what is the largest known natural number?
- dev1n 9y agoNo one can predict the next prime. That's why people want to compute the next prime.
- jordigh 9y agoPrime numbers thin out. We have very good estimates of how they thin out. We also know that gaps between primes can get arbitrarily large. And we cannot predict when the next prime will happen without huge computations. And large primes have a use, e.g. cryptography (although, who knows when we'll have a use for such a large one). Having a list of primes is also very useful for empirical evidence for many conjectures in number theory. None of these things are true about natural numbers in general.
- auggierose 9y agoFor cryptography it isn't very useful to know the largest one. Think about it ... Your other answers amount to: it is difficult, that's why we do it. ?! Sure, just don't expect me to care about it.
- yenwel 9y agoBecause nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer. https://stackoverflow.com/questions/439870/why-are-primes-important-in-cryptography https://stackoverflow.com/questions/439870/why-are-primes-im...
- p1mrx 9y agoIf nothing else, "what's the largest prime number you've found?" would be a fun question to ask another intelligent civilization, should we make contact with one.
- pronoiac 9y agoThere's a site for large prime numbers, and I wondered Mersenne primes have been the largest primes known - since 1992, and since 1952 with an exception for 1989 to 1992. GIMPS - https://www.mersenne.org https://www.mersenne.org - has topped the list since 1996. https://primes.utm.edu/notes/by_year.html#table2 https://primes.utm.edu/notes/by_year.html#table2
- thsowers 9y agoPrevious discussion: https://news.ycombinator.com/item?id=16063946 https://news.ycombinator.com/item?id=16063946