12 ms·
2^74207281-1 is Prime
- coldpie 11y agoBig numbers are fun. Here's some stupid stuff I thought of while reading about this. The number is 2^74,207,281 - 1. Naively stored like a normal integer in memory, that's roughly 75 MB of RAM just to store the number. Compare that to your 64-bit time_t and imagine how long a duration of time could be represented by such a large number. Stored on 3.5" floppy disks for some reason, that's roughly 50 disks just to store the number. Edit: Duh, bits, not bytes. I leave my mistake here for posterity.
- cousin_it 11y agoNot unless you gzip it. Since the number is just the binary 1 repeated a bunch of times, it should gzip pretty well.
- yen223 11y agoRepeated exactly 74,207,281 times, to be precise...
- seibelj 11y agoNo, the number 5 is prime, yet in binary it is 101. The new prime number could have many zeroes interspersed with ones, so you don't know how many 1 digits it has. EDIT: I have realized my mistake in the representation of 2's complement. However, I will leave this here for posterity.
- theandrewbailey 11y agoBut 5 is not 2^n-1
- eggy 11y ago5 is a prime number true, but not a Mersenne prime number. The Mersenne prime number 31 has 5 as its exponent n [1]. [1] http://mathworld.wolfram.com/MersennePrime.html http://mathworld.wolfram.com/MersennePrime.html
- gill984 11y agoIt's a Mersenne Prime, so it is 1 less than some power of 2. This results in all of its non-leading digits in binary being 1s.
- deleted 11y ago[deleted]
- PeCaN 11y agoTurns out run-length encoding it is more or less what you get if you store it as 2^74,207,281 - 1. I imagine this probably is how they store it actually; note that 2^n == 1<<n so you can just store the exponent and complement (74 207 281, 1) and then do normal two's complement math.
- kale 11y agoIf you're talking about storing it in computer memory during calculation, then no, it's written out. The fast MOD operation you list isn't used, it's an FFT using a weight factor that automatically does the mod operation while squaring a number. You start with S[0] = 4, S[i+1] = Si^2 - 2 MOD N. If S[N-2] = 0 then the number is prime. So it's 74,207,279 squares using FFT, each likely more than 75 MiB since there will likely be lots of leading zeros (we're probably close to the maximum number of digits using double precision, round off errors dominate unless you start using really small bases and even greater-length FFTs). That's not counting the two or three compositeness tests that GIMPS uses before starting the Lucas-Lehmer test to prove primality. For several years I've been working on a program to test for primality of the Generalized Fermat numbers, using NTT instead of FFT. NTT is exact (integer math), and the GFNs likely are more "dense" with primes than the Mersenne Numbers. And they also have a faster form to test, although the primality test has a 50% chance of false negative, so you have to run it a few times to be sure a number isn't prime. That's where Mersenne Numbers are easier to test.
- rom1504 11y agoSo I tried it and it's 72135 bytes using tar czf (created by `fs.writeFileSync('/tmp/file',new Buffer(74207281).fill("1"),'utf8')`) Not that it's the most efficient representation at all, 74207281 fits in 4 bytes.
- daveguy 11y agoM49 (for the 49th mersenne prime) fits in 2 bytes! Or even better just 49! 6 bits! Assuming your decompression algorithm is optimized for mersenne primes. :)
- alasdair_ 11y agoIt can fit in a single bit if your algorithm is optimized for "primes that are equal to M49" :)
- graylights 11y agoGreat, I've just discovered the 50th mersenne prime, M50. Decompression takes a lot of time.
- dchest 11y agoThis thread is officially dumb. One guy miscalculates 75 Mbit as ~75 MiB, another guy fills ~70 MiB file with ASCII "1"s.
- 11y ago
- Dylan16807 11y agoIt's the sort of thing that's so repetitive you end up gzipping the gzip, because the "repeat N times" code doesn't support going so high.
- biot 11y agogzipped it's a 9043 byte file when the source is the number expressed exactly as bits. gzipping that 9043 byte file yields a 129 byte file, which gzip can't compress any further. Base64 of the file: H4sICBPHnlYCA2EuYmluegDt0LENQQEUQNHnK7xINF8rLIAVbKH88VU0ZlATK4gt1DQ6vURMoBID iN4CknOa29/BNrN72U+LZj2eL1fxPDU6EXE+3CbvUTEMAAAAAAAAAODfPfq9/DZfx6petw2B32Z5 XZT31mYXH9vDv0RTIwAA
- Houshalter 11y agoI see some redundancy there. The letter "A" appears many times in a row. Also it could be compressed even further. All you need is a computer program that prints "1", 74 million times.
- elenorelange 11y agoIt's already been concisely expressed as 2^74,207,281 - 1, so you don't need a computer program that prints "1" 74 million times. You just need a computer language that can interpret bignum math equations.
- Houshalter 11y agoThat would take ages to compute. Printing one is faster. And might produce the smallest file size if it's done in assembly.
- elenorelange 11y agobut the metric was the most concise way to store the data
- themadcreator 11y agoNeato! Verified with: echo "H4sICBPHnlYCA2EuYmluegDt0LENQQEUQNHnK7xINF8rLIAVbKH88VU0ZlATK4gt1DQ6vURMoBIDiN4CknOa29/BNrN72U+LZj2eL1fxPDU6EXE+3CbvUTEMAAAAAAAAAODfPfq9/DZfx6petw2B32Z5XZT31mYXH9vDv0RTIwAA" | base64 --decode | gzip -d | gzip -d | xxd
- gambogi 11y agoLooks like you just communicated it in 16 bytes though.
- frandroid 11y agoThat's 75 megabits, not megabytes.
- Someone 11y ago75 Megabits; 9.5 MB/7 3.5" floppies/5-10 selfies.
- coldpie 11y agoYou're right! Thanks! I told you it was stupid :P
- DonHopkins 11y agoHow many t-shirts?
- ctdonath 11y agoSomeplace used to print Mersenne primes as posters. IIRC they were using a font around 2 points. Probably given up now...
- ribasushi 11y agoThe person died, and the art with him :( http://www.mersenneforum.org/showthread.php?t=19100 http://www.mersenneforum.org/showthread.php?t=19100
- sanoli 11y agoI remember those. They either came with a loupe, or mentioned explicitly to the buyer that you needed one to see individual numbers. Always wanted to get one. It looked like an all grey poster if you didn't know what it was.
- logicallee 11y ago75 MB compresess neatly to under 12 bytes, which I say because the string "2^74207281-1" is totally unambiguous (Wolfram Alpha will evaluate it for you no questions asked, no guesswork, though obviously it only approximates the output). So the Kolmogorov complexity of the 75 MB is 96 bits or less.
- analog31 11y agoI think there's a related mathematical paradox about the largest number that can be represented by an English phrase of fewer than 93 characters.
- batbomb 11y agoOr you create a new compression scheme just for Mersenne prime numbers where store the exponent. You'll be able to compress the entire number into just 32 bits for several decades at least!
- hinkley 11y agoSince the exponent is prime you should be able to compress it further than that, by simply noting n is the kth prime number. Supposedly as n goes to infinity the probability that n is prime drops to zero, so that should compress handily. Decompressing it, on the other hand, would be pretty slow however. Are primality tests O(n) or O(nlogn)? That puts decompression up to O(n^2) without a pre computed lookup table.
- CUViper 11y agohttps://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number https://en.wikipedia.org/wiki/Prime_number_theorem#Approxima... So with the kth prime ~= k log k, the ratio of primes is 1 / log k. Yes that drops to zero, but very slowly. You can use the upper bound of the kth prime to build a sufficiently large sieve, which can be done O(n).
- spacehome 11y agoIf you don't care about computation time, then why stop there? You can encode the Mth Mersenne with the integer M.
- J_Darnley 11y agoIt is far too many bits to be used for time representation. 512 bits is all that needed to store every planck time (10^-44 seconds) since the big bang until the heat death of the universe (10^100 years).
- PhasmaFelis 11y agoSure, that's fine if all you want is to measure the time from the big bang until the last matter in the universe has evaporated into photon soup. But what if you want the time until those photons are evenly distributed? An article I read a while back estimated that duration as 10^10^78 years, which is absolutely mindboggling and remains the largest number I have ever seen with a real-world physical application. (It may never happen, though; according to Wikipedia, random quantum fluctuations may be sufficient to produce another Big Bang in a mere 10^10^56 years.)
- firethief 11y agoThat makes sense for durations, but a time_t is actually a timestamp. A proper time can have the same units as a duration, but is only useful in conjunction with information about the trajectory of the clock measuring the time. If space is continuous, the amount of information to specify the trajectory is limited only by the capabilities of the measurement apparatus. Of course, for all we know at this point spacetime is quantized; so we should probably hold off on standardizing the time format to end all time formats.
- ramshanker 11y ago22,338,618 digits long, 1 More step towards EFF award for first 100 Million digit prime number.
- pluteoid 11y agoNice. Only the 49th Mersenne yet discovered. This also gives us a new perfect number, 2^(74207281-1)(2^74207281-1).
- JoeAltmaier 11y agoIf you were abducted by aliens, and had memorized that number, you could possibly trade it for wealth in their society. If they hadn't discovered it yet!
- yen223 11y agoIf an alien were abducted by humans, and it memorized a much larger prime number, what would we give in exchange for that piece of information?
- kazazes 11y agoApparently a $3,000 GIMPS research discovery award. What's the practical utility of knowledge of a prime, especially considering that upon announcement it's immediately disseminated?
- zitterbewegung 11y agoThe point of searching for these primes is to motivate research in finding primes so there isn't much practical utility.
- contravariant 11y agoIt's a very large prime number which has a very convenient representation, which makes it useful. You could use it in a Mersenne Twister RNG, for instance.
- scorpion032 11y agoSome Hacker News points, for sure!
- jacquesm 11y agoThe amount of CPU cycles burned to get this result surely translates into some dollar value. Everybody contributes to the MP for free but that doesn't mean there isn't any value involved. It's a donation of sorts.
- 11y ago
- jlewallen 11y agoGlad I actually read the article because I never would have known this: "The official discovery date is the day a human took note of the result. This is in keeping with tradition as M4253 is considered never to have been the largest known prime number because Hurwitz in 1961 read his computer printout backwards and saw M4423 was prime seconds before seeing that M4253 was also prime."
- NelsonMinar 11y agoAlso "Dr. Cooper's computer reported the prime in GIMPS on September 17, 2015 but it remained unnoticed until routine maintenance data-mined it." I'd have thought that BIG FLASHING LIGHTS would go off if a prime were reported. Maybe with CELEBRATORY KLAXONS.
- anonymfus 11y agoE-mail notification failed according to Professor Curtis Cooper in interview for Matt Parker's "Standup Math" youtube channel: http://m.youtube.com/watch?v=q5ozBnrd5Zc http://m.youtube.com/watch?v=q5ozBnrd5Zc
- banku_brougham 11y ago
- banku_brougham 11y agoI love this. So M49 is now the largest known prime, but what does it take to find the next prime number? Or any larger prime?
- dexterdog 11y agoA buttload of electricity
- haberman 11y ago> The primality proof took 31 days of non-stop computing on a PC with an Intel I7-4790 CPU. How does this work? You just try to divide by every possible number and ensure the result isn't an integer?
- ajuc 11y agoYou only need to divide by prime numbers up to ceil(sqrt(your_number)). They don't know all prime numbers up to this number, but they can easily exclude many numbers (for example even).
- kale 11y agoThat would still take an eternity. They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor). If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time. Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.
- skj 11y agoOr any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.
- spdionis 11y agoThis are the simplest insights for optimizing primality test. A nice exercise to implement if you like algorithms. More info: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes
- saganus 11y agoI believe they actually have very optimized algorithms to test for primality [0], which not necessarily involve diving by every possible number. There are simple tests and there are more complex ones, that use probabilities and other workarounds to avoid having to divide by every possible number. [0] https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test
- kylnew 11y agoI'm curious to understand the significance of finding the largest known prime numbers. It seems that some people get pretty excited but I'm not sure if it's just purely academic or there's some useful applications I'm unaware of. Can anyone enlighten me?
- ravanpao 11y agoI am curious too. I wonder if this has anything to do with the public key encryption relying on prime numbers. EFF has a bounty for large prime numbers: https://www.eff.org/awards/coop https://www.eff.org/awards/coop "The EFF awards are about cooperation," said John Gilmore, EFF co-founder and project leader for the awards. "Prime numbers are important in mathematics and encryption, but the real message is that many other problems can be solved by similar methods." Finding these prime numbers will be no simple task, given today's computational power. It has taken mathematicians years to uncover and confirm new largest known primes. However, the computer industry produces millions of new computers each year, which sit idle much of the time, running screen savers or waiting for the user to do something. EFF is encouraging people to pool their computing power over the Internet, to work together to share this massive resource. In the process, EFF hopes to inspire experts to apply collaborative computing to large problems, and thereby foster new technologies and opportunities for everyone.
- tinalumfoil 11y ago> However, the computer industry produces millions of new computers each year, which sit idle much of the time, running screen savers or waiting for the user to do something. Considering how much more electricity a running computer uses versus an idle one and how much faster consumer CPUs degrade under load this definitely seems like a huge waste of resources for something that has little, if any, utility.
- organsnyder 11y agoI used to run prime95 on all of my machines, back when power management (especially on desktops) was virtually nonexistent. Obviously, with the power management features we have now, an idle CPU (especially outside of a hosting environment) is not considered wasteful.
- jacquesm 11y agoWow, many years since I've contributed to the project with my little cluster, nice to see them still going strong. Incidentally, the project source code contains one of the fastest Fourier transform implementations that I'm aware of.
- nitrogen 11y agoDo you happen to know how it compares to kissfft or fftw?
- jacquesm 11y agoGood question, no, no idea but of those two fftw would appear to have the edge so if you're going to compare do it with that one. I do know the fftw guys benchmarked an older version of it but I can't find the results (there used to be a bunch of graphs showing the relative performance of all those ffts listed). It should be fairly easy to figure this out though, the benchmark code is public and if fft sizes you are interested in are known you could make a very precise comparison. One warning about the mersenne fft code, it is not the most readable one on account of all the optimizations, but if all you're interested in is a drop-in library then it might suit your needs, especially if the size fft you're after is one that has already been optimized to the hilt by the mersenne project people. If you find you need to customize it then you're probably better off with a more universal implementation, even at the expense of some cycles.
- legohead 11y agois there anything special you can do with mersenne primes? if there's no pattern to them, can't it just be seen as dumb luck?
- syncsynchalt 11y agoThey represent the largest known primes, as the special case 2^n-1 allows us to verify their primeness using a method much more efficient than checking all potential factors. So to answer your question, if there's ever a need for ridiculously large numbers that are known to be prime this is how we'll fill it. Short of that need, it's still fun as a mathematical world record!
- agentgt 11y agoI had to find out what a Mersenne number was again (vaguely remember but forgot) and I was shocked to find this problem in mathematics: "It is not known whether or not there is an odd perfect number, but if there is one it is big! This is probably the oldest unsolved problem in all of mathematics." [1] [1]: http://primes.utm.edu/mersenne/index.html http://primes.utm.edu/mersenne/index.html
- gitpusher 11y agoMeanwhile, somewhere in Wisconsin, the number 274-207-2811 is being mercilessly prank-called my mathematicians.
- technotaoist 11y agoI downloaded and checked the zip file. Last digit is a 6. Downloaded it multiple times to test. Can anyone else replicate this?
- i_cannot_hack 11y agoIf I have read it correctly, the last digit is a 1. This is the end of the file I downloaded: ...010073391086436351 Edit: Confirmed by https://www.youtube.com/watch?v=q5ozBnrd5Zc https://www.youtube.com/watch?v=q5ozBnrd5Zc
- technotaoist 11y agoI'll try a different tool to decompress the file maybe. a 6 would have made no sense. What was your uncompressed file size? I ended up with 44.7MB
- wrboyce 11y ago% tail -1 M74207281/M74207281.txt 010073391086436351 % du M74207281/M74207281.txt 44504 M74207281/M74207281.txt % md5 -q M74207281/M74207281.txt 53294de131970c2cee8da6fe9a3135b3
- monochromatic 11y agoHere are the last "few" digits: 7302483892184777905493456249144515504366 7354352576469730088553216748038660370944 9872555291212307480179276559709617648630 5356033886997788467889060830923906229428 0028777084668153501142762292122183690404 5477963931367013401448014940470411696633 4745646885160717774014762912462113646879 4258014451073931002129271816293359314942 3901821387921767116495628719049868701007 3391086436351
- hinkley 11y agoAre there any double Marsenne primes that we know of? Where 2^(2^n - 1) - 1 is prime as well?
- evandijk70 11y ago2^3-1 = 7 => prime 2^7-1 = 127 => prime 2^127 - 2 is also prime
- evandijk70 11y ago2^3-1 = 7 => prime 2^7-1 = 127 => prime 2^127 - 2 is also prime
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- Consultant32452 11y agoI have a stupid question that will reveal how I know nothing about cryptography. I understand that large primes are somehow important for some types of cryptography. How are there not just databases of large primes that make breaking the types of cryptography that rely on large primes trivial?
- xyzzyz 11y agoThere are _a lot_ of large primes. If you randomly choose a 1024 bit prime, it's _extremely unlikely_ anybody seen or used that prime before you.
- laughinghan 11y agoThere are too many. Not just more than could fit in every database on Earth. More than could fit on every database if every star in the sky had an Earth, each with as many databases as there are on Earth. This is nothing specific to cryptography or prime numbers. Fun fact: if you shuffle a deck of cards correctly, it's almost certain that no one in history has ever had a deck in the exact same order. https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml
- Consultant32452 11y agoI understand that there's a huge number of primes, but surely the primes being used to generate keys or whatever process they're involved in are "known" primes, right? It's not as if when I try to encrypt something my machine is going to search for a new prime number that hopefully won't get guessed.
- yoha 11y agoLong prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). Then, you do search for "a new prime number that hopefully won't get guessed". It can take from a few seconds to several minutes, depending on the hardware and the desired key length. The usual approach is to take a random odd number of desired length and then have a probabilistic primality test (much faster than what would be needed for a formal proof). Several attacks rely on bad entropy or bad pseudo random number generators (PRNG) to guess what prime was selected.