2^74207281-1 is Prime

Re:2^74207281-1 is Prime by hinkley on Tuesday January 19, 2016 @05:17PM (#10934547)

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.

[ Parent | on HN ]

Re:2^74207281-1 is Prime by CUViper on Tuesday January 19, 2016 @06:38PM (#10934982)

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).

[ Parent | on HN ]

Re:2^74207281-1 is Prime by spacehome on Wednesday January 20, 2016 @01:17AM (#10936356)

If you don't care about computation time, then why stop there?

You can encode the Mth Mersenne with the integer M.

[ Parent | on HN ]

Re:2^74207281-1 is Prime by hinkley on Wednesday January 20, 2016 @01:55PM (#10940399)

But then I have to keep patching the code every time a new one comes out. Too hard!

[ Parent | on HN ]

Re:2^74207281-1 is Prime by spacehome on Wednesday January 20, 2016 @10:45PM (#10943221)

You don't. You can write a program that converts between m and M_m. It just takes a long time to convert.

[ Parent | on HN ]