H4sICBPHnlYCA2EuYmluegDt0LENQQEUQNHnK7xINF8rLIAVbKH88VU0ZlATK4gt1DQ6vURMoBID
  iN4CknOa29/BNrN72U+LZj2eL1fxPDU6EXE+3CbvUTEMAAAAAAAAAODfPfq9/DZfx6petw2B32Z5
  XZT31mYXH9vDv0RTIwAA

  echo "H4sICBPHnlYCA2EuYmluegDt0LENQQEUQNHnK7xINF8rLIAVbKH88VU0ZlATK4gt1DQ6vURMoBIDiN4CknOa29/BNrN72U+LZj2eL1fxPDU6EXE+3CbvUTEMAAAAAAAAAODfPfq9/DZfx6petw2B32Z5XZT31mYXH9vDv0RTIwAA" | base64 --decode | gzip -d | gzip -d | xxd

Also it could be compressed even further. All you need is a computer program that prints "1", 74 million times.

You just need a computer language that can interpret bignum math equations.

Not that it's the most efficient representation at all, 74207281 fits in 4 bytes.

Oh, and I also forgot to mention that the guy used `tar` for compressing one file. I'll see myself out.

EDIT: I have realized my mistake in the representation of 2's complement. However, I will leave this here for posterity.

[1] http://mathworld.wolfram.com/MersennePrime.html

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.

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

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.

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

You can encode the Mth Mersenne with the integer M.