5 ms·
Not unless you gzip it. Since the number is just the binary 1 repeated a bunch of times, it should gzip pretty well.
by cousin_it 11y ago
Not 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