New values of pi(x) (19 Jun 1996)

New values of pi(x)

Date: Wed, 19 Jun 1996 16:16:11 +0200
From: Marc Deleglise
To: Chris Caldwell

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

pi(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
These values have been checked
  1. 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.
  2. or by computing them two times with different values of 2 parameters y and z used during the computation.
Thanks to Paul Zimmermann from INRIA Nancy who lend me some days of computation on his machines, (and also some hours of his time to compile the program on these machines!), and between other values got the pi(418....) = 10^17.

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