[See the previous note of 18 Apr 1996]

I am pleased to send you some new values of pi(x): ( 2e18 means 2.10^(18) and so on...)

These values have been checkedpi(2e18) = 48 645 161 281 738 535 pi(3e18) = 72 254 704 797 687 083 pi(4e18) = 95 676 260 903 887 607 pi(4185296581467695669) = 100 000 000 000 000 000 pi(5e18) = 118 959 989 688 273 472 pi(6e18) = 142 135 049 412 622 144 pi(7e18) = 165 220 513 980 969 424 pi(8e18) = 188 229 829 247 429 504 pi(9e18) = 211 172 979 243 258 278 pi(1e19) = 234 057 667 276 344 607 pi(2e19) = 460 637 655 126 005 490 pi(4e19) = 906 790 515 105 576 571 pi(1e20) = 2 220 819 602 560 918 840

- by computing pi(x) and pi(x + 1e7) and checking that the number of primes in the short interval agrees with the two values of pi.
- or by computing them two times with different values of 2 parameters y and z used during the computation.

The method is presented in Math of Comp 1996 by Deleglise & Rivat: Computing Pi(x), the Meissel, Lehmer, Lagarias, Miller, Odlyzko method [DR96]. The program is an improved implementation of the precedent version. The asymptotic time and space complexity are unchanged (O(x^(2/3)/logx^2) for time and O(x^(1/3)logx^3) for space);

pi(1e19) took 40 hours of computation on a DEC-Alpha 5/250 and needed about 80Mo memory. pi(1e20) took 13days of computation on a DEC-ALPHA 5/250 (because of lack of memory, we had to exchange space against time) and also 13days on a R8000.

Marc Deleglise