From: xavier.gourdon@online.fr (Xavier Gourdon) Subject: New record computation for pi(x), x=10^21 Date: 27 Oct 00 16:13:17 GMT Newsgroups: sci.math.numberthy Summary: [missing] I am pleased to send you the value of a new record computation of pi(x) = #{p<=x, p prime) : pi(10^21) = 21 127 269 486 018 731 928 As always, this is close to the corresponding values of Li(x) = int_2^m dt/log(t) and R(x) = \sum_{n>0} mu(n)/n Li(x^{1/n}) : Li(10^21) - Pi(10^21) = 597 394 254 R(10^21) - Pi(10^21) = -86 432 204 CHECK : This value has been checked by computing pi(10^21+10^8) with a different parameter y used in the algorithm, and by counting the number of primes in the inverval (10^21, 10^21+10^8]. The implementation was also checked on preceeding known values of pi(x) computed by Marc Deleglise, (see http://www.utm.edu/research/primes/notes/md.html) including Pi(10^20), Pi(2.10^19), Pi(10^19) and Pi(10^18). TIME AND MEMORY : The computation was distributed on two machines and took 20 days (equivalent total time on Pentium II 350). The verification took approximately the same time. The memory needed was approximately 115 Mo. ALGORITHM : The algorithm used is a technical improvement of the algorithm in Math Of Comp 1996 by Deleglise & Rivat : Computing Pi(x), the Meissel, Lehmer, Lagarias, Miller, Odlyzko method. The asymptotic time complexity remains unchanged O(x^{2/3}/log(x)^2), but some constant factors have been saved. The asymptotic space complexity has been decreased a bit, by a factor log(x) at least (I did not make precise asymptotic study for this). A new feature has been introduced in the algorithm, permitting to distribute the computation on several machines with NO MEMORY EXCHANGE (expect the final result of each computation, which has O(log(n)) bits), provided a precomputation taking time O(x^{1/2}/log^{9/2}(x)) is done on each machine. The problem of distributing the pi(x) computation by this algorithm have already been considered in Computing pi(x): An analytic method, J. C. Lagarias and A. M. Odlyzko, J. Algorithms, 8 (1987), pp. 173-191, but memory exchange was needed. More information will be soon available on my web site : http://xavier.gourdon.free.fr/Constants/constants.html I am also planning to start a project for a distributed computation on the web to compute values of pi(x) for values of x between 10^21 and 10^24. Best regards, Xavier Gourdon