Re:2^74207281-1 is Prime
by batbomb on Tuesday January 19, 2016 @02:46PM
(#10933400)
Or 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!
[ Parent
| on HN ]
Since 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.
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).
If you don't care about computation time, then why stop there?
You can encode the Mth Mersenne with the integer M.
But then I have to keep patching the code every time a new one comes out. Too hard!