9 ms·
The 10,000,000,000th Prime Number (1994)
- JoeAltmaier 6y agoConcrete proof there is no largest prime number: color the number line starting at zero, blackening every other number, every third, every fifth and so on up to every 'theoretical-biggest-prime'. Calculate PIPrime, the product of all of the prime numbers. All of these blackening sequences land on that number (its a multiple of all of them). Note that the blackened-integer sequence is symmetrical from zero to PIPrime - same forward and backward. In fact it starts to repeat itself from there. Now note that '1' was not blackened. So of course, the number to the right or left of PIPrime is not blackened. So that number must also be prime (not a multiple of any known prime) or there is some other prime number, larger than the known largest, that would have landed there. In either case, there is a larger prime than you knew.
- JoeAltmaier 6y agoi.e. 'concrete mathematical' proof, a proof constructed from physical references rather than algebraic manipulation
- lmilcin 6y ago455,052,512 is obviously not a prime so this must be an error in the article.
- quietbritishjim 6y agoThe article claims that to be the number of primes less than 10e10, not that it is a prime itself.
- csours 6y agoI misread that the same way you did.
- gerdesj 6y agoHui's immediate response was, "Do you start counting from 0 or 1?" Counting numbers are defined as the integers starting from one. I'm probably lacking a bit of rigour there. err ... Define 1 = S or is that S = 1 or S is a thing or 1 is a thing or something and then put more S (s) in until you run out of S (essessses) then you have reached infinity. If it's not a really big infinity then keep adding S (sssssss) or remove a few and add some more. You'll get there eventually - lots of Ss or infinity, or not, who knows? If you run out of S then try adding some T. Everything is better with T. He would have better off with: "Do you prefer green trees or brown trees?" That would have simply sounded silly, rather than +1 insightful.
- beervirus 6y agoYeah that comment didn’t make much sense. No one would seriously dispute that 2 is the first prime.
- klyrs 6y agoNot so! Some, quite seriously, consider -1 to be prime. John Conway was such a person.
- gerdesj 6y agoMr Conway was (RIP) a genius. If he says -1 is prime ... it's prime. End of.
- gowld 6y agoLol check this out https://www.google.com/search?q=is+-1+prime https://www.google.com/search?q=is+-1+prime More seriously http://mathforum.org/library/drmath/view/55958.html http://mathforum.org/library/drmath/view/55958.html But the link to details is dead.
- Muskwalker 6y agoInternet Archive suggests the original discussion was a Usenet thread; here is the link to Google Groups' version of it: https://groups.google.com/d/topic/geometry.research/7pyFhAAye1E/discussion https://groups.google.com/d/topic/geometry.research/7pyFhAAy...
- svat 6y ago(1994). The article is a story, about how Roger Hui (who with Kenneth E. Iverson developed the programming language J), set about finding the 10 billionth prime: by the Prime Number Theorem it should be about 10^10*log(10^10) which is less than 270 billion, so he split the range into 270 parts, and had each of several machines pick up one part and sieve that billion-number range (to count the number of primes), a million integers at a time. After 20 hours (on 60-70 workstations) he had the counts, so knew the exact million-integer range in which the prime occurred, from which the 10 billionth prime turns out to be either 252,097,800,629 (with 2 as the 0th prime) or 252,097,800,623 (with 2 as the 1st prime). After doing this, he was able to correct an off-by-one count in a table in a printed book, but the real moral of the story is that this is of course a poor way to compute the nth prime for large n: it has been known since the 1800s how to quickly compute pi(x) (the number of primes not greater than x), and using a published algorithm known at the time would have let him find the ten billionth prime in less than 3 minutes instead of thousands of hours of computer time. That's the article (though I've focused more on the algorithm while it says “this column is not so much an article about programming as it is about computer logistics”), but these days we can just hit up https://www.wolframalpha.com/input/?i=the+ten+billionth+prime https://www.wolframalpha.com/input/?i=the+ten+billionth+prim... or https://primes.utm.edu/nthprime/index.php#nth https://primes.utm.edu/nthprime/index.php#nth or enter "prime(10000000000)" into https://live.sympy.org/ https://live.sympy.org/ (this times out for some reason, though primepi(22801763489) takes less than a minute so you could binary-search manually), or enter "nth_prime(10^10)" into Sage (https://www.sagemath.org/ https://www.sagemath.org/) to get the result pretty much instantly (after it starts up, which takes a while), or....
- blackrock 6y agoRemind me again, what are some of the benefits to finding ever larger prime numbers? Not that there is anything wrong with doing so. Was it to enhance public key encryption possibilities?
- xelxebar 6y agoIt's more about the techniques developed along the way than the actual number itself. What's the point of running a marathon? Is it to expand your hunting range?
- gregfjohnson 6y agoThe stated moral of the story (last line of the article): "Brains win again over brawn: a well-designed, mathematically knowledgeable algorithm beats brute force!" This reminds me of a claim I heard from a numerical analysis colleague: "Algorithms of today running on hardware from the 1950's would beat algorithms of the 1950's running on hardware of today." It was a thought-provoking comment. It would be less hyperbolic if prefaced with "There exist some problems of practical significance for which.." The question is, what might be some examples? What are some problems for which the time or space complexity of the best known solution has decreased over the last several decades to the point that the above statement would be true of them?
- kens 6y agoThe Fast Fourier Transform (1965) is one very important algorithm that comes to mind, speeding up Fourier Transforms from O(N^2) to O(N log N). Quicksort (published 1961) might be another example, but since sorts in the 1950s usually ran on tape drives, it's hard to compare. On the whole, computers of the 1950s were extremely memory-limited, so many modern algorithms aren't entirely relevant. For example, the IBM 7090 (1959) was a large-scale scientific computer and had an address space of 32K words. As for performance, it did 39,500 multiplications per second. A modern supercomputer is trillions of times faster; that makes up for a lot of bad algorithms. Most modern problems are going to have a hard time fitting in a 1950s computer, regardless of the algorithm. On the whole, I think you'd be better off with 1950s algorithms on a modern computer than vice versa. On the other hand, modern cryptographic algorithms on old hardware would be infinitely better than old algorithms on modern hardware.
- rstuart4133 6y agoMerge sorts are typically used when sorting data on magnetic tapes. Polyphase merge was popular. All merge sorts are O(N log(N)). They were ideal for tapes as they read and write data sequentially.
- rsecora 6y agoThis is why I love HN. I was going to the shelving to check the cost in the Wirth book [1], and the right number was already published in HN. [1] Algorithms + Data Structures = Programs / Niklaus Wirth.
- nautilus12 6y agoBrains may win over brawn, but the problem is that brains don't generalize. It requires bespoke creative mathematical work. In that sense, the brute force method while slower has an advantage in that it could theoretically be derived more easily (from another algorithm for example or by a general intelligence system). Direct analytical results are always faster and more accurate than numerical results, but numerical results are more reliably attained.
- chenglou 6y agoTurns out, we end up evolving said general intelligence system into doing bespoke creative work, and it slows down the compilation time by around as much as it takes a human to think up the analytical solution =P Then we end up with a tunable knob to speed up compilation. But then this more or less reduces to coding up either method depending on the situation, aka what we began with!
- nautilus12 6y agoValid point! I think you are right about this
- dvirsky 6y ago> Even a Boolean vector taking just 1 bit per element would have to be more than 3e10 bytes long, so it was clear that the problem had to be partitioned. That's 28GB. That's just astronomical in those days' terms, even stored on hard drives it would have taken a massive array of commodity HDDs. I love these little reminders of how far we've come.
- pvg 6y agoThere were 0.5 to 2gb drives around then as were commercial offerings for arrays that could easily store 28. The growth has been huge, of course, but the mid 90s weren't entirely the stone age either. https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=897/ENUS9394-001&infotype=DD&subtype=SM&appname=skmwww https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=8...
- dvirsky 6y agoOf course, but you'd still need an array of a few dozens of those.
- pvg 6y agoRight but it's hardly astronomical and something that easily fit on a single array. My 1996 (work) workstation had about 9gb in regular drives hooked up to it. A lot, but nothing astronomical. DVDs were just around the corner, for another point of context.
- dvirsky 6y agoAstronomical referred to memory, for disks I called it "massive".
- pvg 6y agoHah, I have pendaticornered myself with the astronomical. I guess a better way of putting it is - 1 gig drives came out in 91, the 2 gig barracuda in 92. By 94, typical personal device storage would be a bigger fraction of 30 gigs than, say, current typical personal device storage as a fraction of a current backblaze 4u pod. A backblaze pod is pretty mundane.
- barrkel 6y ago> Brains win again over brawn: a well-designed, mathematically knowledgeable algorithm beats brute force! But it didn't, though, did it. Brute force got an answer before brains found the smarter way. It's great that the well-designed, math knowledgeable algorithm beats brute force, but it takes time to design something well, and to gain the knowledge, if it even exists, which is not a guaranteed prior. In the meantime, your quickly written brute force approach can be making progress. IMO always try brute force first if there isn't a fairly obvious alternative. Surprisingly often, brute force is enough.
- benchaney 6y agoThat seems highly questionable. Given the complexity of his brute force algorithm, it was probably significantly more complex, and required more development time than the more elegant solution. The only reason the brute force got its answer first, was because it was the first thing he tried. That’s hardly an advantage of the approach.
- rlonn 6y agoIf you know how to do something, it is usually a lot faster to do it that way, than go looking for alternative solutions. The mantra of highly productive people: Start where you are. Use what you have. Do what you can.
- benchaney 6y agoThis is what I found doubtful. Generally implementing and debugging complex solutions is very time consuming and self education is very efficient.
- barrkel 6y agoWhat you're missing is the discovery time of the elegant solution, and the knowledge required to know that it may exist.
- benchaney 6y ago
- chrismsimpson 6y agoLet's not an say we did