GIMPS Project Discovers Largest Known Prime Number
mersenne.org
mersenne.org
Perhaps you were joking; but I'm sure others might be confused.
Literally, the first thing I though of was GIMP as well :)
One of my favorite jokes of all time was pg's nickb april fools prank: https://news.ycombinator.com/item?id=151109#152361
Probably worth putting together a list of HN moments... There were so many.
- Demetri Martin
The current plan is to create a "mirror" of HN's front page, but with a smaller community. You'll be bale to keep your HN name, because you won't be allowed to use someone's existing HN name on the new site unless you claim it.
Then, we'll need content. This was the secret sauce in the early HN days. The sole reason for people to come to the new site would be good conversation, and I think recruiting a few of the writers from HN would be enough to bootstrap it. Part of HN's early success was that pg actually participated in HN. Whereas the current mod team just shows up to beat us over the head and little else.
If you want to help plan this out, contact me (email's in profile). I think we have a shot at this. Some past thoughts on the topic:
https://news.ycombinator.com/item?id=16064078
https://news.ycombinator.com/item?id=16044466
Getting away from the heavy-handed moderation will be the best part. Comments will be free to flow into tangents, as long as they're substantive.
What a great story.
https://math.stackexchange.com/questions/272791/how-many-pri...
> Nobody's really keeping count. ... There are very many hundred-digit primes to find. We could cover the Earth in harddisks full of distinct hundred-digit primes to a height of hundreds of meters, without even making a dent in the supply of hundred-digit primes.
(Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B")
Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes.
Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"
We already know the primality of all primes. They're prime. All numbers though . . .
[0]: https://wiki.openssl.org/index.php/Manual:BN_generate_prime(...
See https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_..., https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_...
Also, for those that are concerned about doing statistical primality tests, there are fast deterministic tests (https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...). Read https://en.wikipedia.org/wiki/AKS_primality_test for pointers to the algorithms to use in practice.
(I haven't personally understood the probabilistic primality tests well enough to understand how they guarantee that the probability of error contributed by each round of the test is completely independent of every other round.)
Primality testing is not trivial at those number sizes
https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...
There's no known general-form primality test that is nearly as fast for numbers of corresponding sizes.
Primes are really really common.
It is trivial (in computational power) to find a random prime in order of 2^2048. So such a list would be way to big to store somewhere and always be out of date. It is not hard to find very big primes. It is just hard to find very very big primes.
This isn't the exact question you're asking, but we actually know the distribution of prime numbers, which allows us to calculate the (approximate) number of primes that are less than or equal to an arbitrary value.
Since the largest prime discovered is 2^(277,232,917-1), that means that the number of primes less than or equal to that number is approximately equal to 2^(277,232,917-1)/ln(2^(277,232,917-1)).
That's approximately equal to:
2^(277,232,917-1)/ln(2^(277,232,917)), which is in turn equal to 2^(277,232,917-1)/(277,232,917 * ln(2)).
That's a number that's too big to plug into your standard everyday calculator, but that tells you the number of primes you could "discover" and still not break the (new) record.
2^(277,232,917)-1
not
2^(277,232,917-1)
(2^77,232,917)-1
2 ⁷⁷ ²³² ⁹¹⁷ − 1
not
2 ⁷⁷ ²³² ⁹¹⁷ ⁻ ¹
There, no more ambiguity.
(Now I’m waiting for someone to jump on me to correct anything subtle.)
[Ah, I see, the parentheses were indeed a red herring. Ah well; let the superscripts remain.]
The occurrence rate is surprisingly (or not?) irregular.
Given an ordered list of primes {2,3,5,...,n} one (of several) immediately known next prime number is simply (2 x 3 x 5 x ... x n) + 1. We know that number's prime because it cannot be cleanly divided by 2, or 3, or 5, or ..., or n.
As such, even if it might be useful to have a list of all known primes, annotated with what kind of prime each number is, such a list cannot be constructed: even just the subset of all prime numbers generated based on the simple above rule would be infinitely long, just like the list of all even numbers is infinitely long.
One answer is a bit buried in a sub link in the article. On that page, you’ll find arguments for the following reasons: tradition, by products of the quest, collection of rare mathematical things, glory, pushing hardware performance, and contest rewards.
Personally I’m forced to admit I enjoy seeing them found while being unable to form any cogent justification.
- George Mallory
I was watching a math documentary and one example was a Cicada in North Carolina that only emerges once every thirteen years millions of them at once. It's a defense mechanism the sheer number overwhelms predators. The Cicada does this also to avoid appearing when another species of Cicada appears to prevent cross breeding.
The other species in the same region emerges every 7 years. The two will only emerge at the same time every 220 years (I think it as).
Smart bugs!
Edit: I looked it up, its 13 and 17 years, giving a 221 year overall cycle. I guess it only really "matters" that the years are coprime.
I know at least one sysadmin who used GIMPS as a burn-in program for new servers.....
> Mersennes are beautiful and have some surprising applications.
https://en.wikipedia.org/wiki/Euclid%E2%80%93Euler_theorem
(combining two of history's greatest mathematicians with names that have confused generations of students by being pronounced very differently)
The earliest remaining editions of the Elements have no author mentioned, and our source that Euclid compiled it is a brief remark from Proclus 700 years later. Most of what is in the Elements was results from earlier, and it’s all but impossible to break down which bits were first done when or by whom. Most of what we can see today of the Elements or Euclid’s other books is later copies, much of it probably added/changed/reordered/... later.
If you want a 2000-year-old idol, go for Archimedes.
In the last 1000 years, the most influential mathematician is surely Newton, with an honorable mention for Leibniz. For the computer age (from 1950 through the upcoming few centuries), I’d put my vote on Grassmann (1809–1877), though his work was long ahead of its time and still substantially underappreciated.
Euler and Gauss were of course both brilliant and prolific and well worth studying, along with Descartes, Lagrange, Riemann, Poincaré, ....
x ≡ x mod 2^q + ⌊x/2^q⌋ (mod p).
Another application of slightly larger Mersennes is https://en.wikipedia.org/wiki/Mersenne_Twister
It needs to comply with the 2^n-1 formula. Let's say I want a number long 100 000 000 or even 1 000 000 000 long. Or a prime above that length.
Do you know how much would that cost per number prime and non-prime?
Yes, I'm weird: I prefer to do computation for BOINC than for bitcoin. :-)
on a general purpose system you can use GPUs and BOINC with SETI, not sure about GIMPS.
I do have some PC systems but they are shared among family members, making it difficult to run BOINC as a background task without interfering with their work.
I'll look at low-cost systems, like the Raspberry Pi, to see if I can use them as dedicated BOINC boxes instead.
There have been interesting discussions about a cryptocurrency whose proof of work task would be something in some way more interesting or more useful than partial hash collisions, but I don't think many such systems have caught on. There is a prime-related one called Primecoin:
https://en.wikipedia.org/wiki/Primecoin
So, I guess that's a precedent for creating new cryptocurrency designs that do something else. I don't know if there's a way to make any of the BOINC tasks into cheap-to-verify PoW systems or if anyone's tried to do so, but that might be a cool project.
It's mostly just running an algorithm for long enough to pay off.
"Now Bruce Schneier needs to change the code on his luggage"
I see a similar phenomenon with press. They "hype" something they barely understand, change parts of the story to make it more interesting, or invent new words (Cyber!). This is a disservice.
What do you do to avoid this noise?