tables of p(n) and/or pi(n)

[Joshua Zucker]

On 9/18/05, Hans Havermann <pxp at rogers.com> wrote:
> Earlier this year, I built myself a database of the first 10^9 primes in
> chunks of 10^7 numbers per file. Each file is roughly 100 MB, implying that
> if I were to try to duplicate the 10^12 numbers mentioned in your reference,
> I'd be looking for 1 TB of memory (excluding compression schemes)! How many
> primes can you afford to own? :) 

The easy compression fits 30 numbers per byte, by using one bit for
prime/not prime for each of the number equal to 1, 7, 11, 13, 17, 19,
23, 29 mod 30.

So it's not 30 primes per byte, but rather 30 numbers.

With that scheme, since pi(3*10^13) is roughly 10^12, it would take
only (3*10^13)/30 bytes to store the primality of all of them, so
indeed, 1TB is about right (not 10TB as in your corrected post).

Maybe there are better ways to store it?

--Joshua Zucker