Pi(x) value for x at 10^16 size

[edorajh]

Is there any tool or software that can return pi(x) value for numbers at 10^16 size?

[CRGreathouse]

Edit: see below.

[axn]

Not quite what you were looking for: https://primes.utm.edu/nthprime/

[CRGreathouse]

Originally Posted by axn

Not quite what you were looking for: https://primes.utm.edu/nthprime/

A great tool, very fast and nothing to install, but 3 * 10^13 < 10^16.

[danaj]

https://github.com/kimwalisch/primecount

The currently fastest available implementation. Threaded as well. You definitely would want to use instead of primesieve. Same author.


Perl/ntheory (available with Strawberry Perl, or install Math::Prime::Util from your distro or CPAN). perl -E "say prime_count(1e16)"

Used to be just a little faster than primecount, but Kim has done some fantastic work and made his faster, and once you get to use multiple threads it is a lot faster at this size. For 1e16 it is about 21 seconds for Perl/ntheory, and Kim reports 2.67 seconds multithreaded for his latest code. Wow.

[R. Gerbicz]

Originally Posted by CRGreathouse

A great tool, very fast and nothing to install, but 3 * 10^13 < 10^16.

This is similar to the Mathematica's idea, and it is very good for "smallish" x<=N values: up to some limit N compute the primes, and store the count at each n==0 mod S.

primepi(x)=primepi(c)+#{p:c<p<=x}, where c=S*floor(x/S), and here primepi(c) has been precomputed. (or use c'=c+S if x mod S>S/2)

Making a table for N=10^16 and for say S=10^8 wouldn't be that hard, you need less than 1GB of Ram to store the table. Using this setup it would take much less than 1 sec to get primepi(x) for any x<=10^16.

[danaj]

Originally Posted by R. Gerbicz

Making a table for N=10^16 and for say S=10^8 wouldn't be that hard, you need less than 1GB of Ram to store the table. Using this setup it would take much less than 1 sec to get primepi(x) for any x<=10^16.

I use stepped tables for N < 3e9 using 4k of data. There's a script included with my package that takes parameters step/start/stop and creates tables ready to plug in to the header file. Extending that to 3e10 with 3e8 steps goes to 8k and is well under a second to get values. Extending to 3e11 with 3e8 steps is 44k of table data and still well under a second.

My table generator gets pretty slow at these sizes as it wasn't really intended for that. It'd make more sense to load up TOeS's extensive count tables and build something using those, though they're lacking in resolution vs. the 1e8 (or 3e8) target (as are Nicely and Kulcha's tables). They have what we need to 1e14 though.

For my implementations, past 66M is slower than just running LMO. Using those steps it looks like it would cross over somewhere in the 8e12 range. There exist faster sieves and a faster LMO which would modify those numbers. Table sizes would probably come out to under 1GB for 10^16.