4 ms·
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
by batbomb 11y ago
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!
- 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.