pi(x) project
 

I found this [URL="http://numbers.computation.free.fr/Constants/Primes/Pix/pixproject.html"]pi(x) project[/URL] page. They found pi(10^23) but it had a +-1 error.

I was wondering how do they actually calculate pi at those ranges, I mean there are 1.724*10^21 primes between 10^22 and 10^23 ([URL="http://mathworld.wolfram.com/PrimeCountingFunction.html"]http://mathworld.wolfram.com/PrimeCountingFunction.html[/URL]), they can't actually prove all those numbers prime?

Anyone continuing pi(x) above 10^23?

From SeqFan:[quote="Ralf Stephan"]

> I used Mathematica, which fortunately has some sophisticated pi(x) routines
> built-in. The implementation notes say that the Lagarias-Miller-Odlyzko
> algorithm (an improvement on the Meissel-Lehmer Algorithm that I once knew

I once was interested in that and digged up some references
but the implementation was well over my head...

[url]http://www.ams.org/journal-getitem?pii=S0025-5718-96-00674-6[/url]
[url]http://citeseer.nj.nec.com/8559.html[/url]
[url]http://numbers.computation.free.fr/Constants/constants.html[/url]
and Marc Deléglise habilitation

On the Lagarias-Odlyzko algorithm:
[url]http://www.math.uiuc.edu/~galway/SlidesETC/thesis-slides-98.pdf[/url]
[url]http://www.math.uiuc.edu/~galway/SlidesETC/thesis-slides-98.ps.gz[/url]


ralf[/quote]

[QUOTE=ATH;70737]I was wondering how do they actually calculate pi at those ranges, I mean there are 1.724*10^21 primes between 10^22 and 10^23 ([URL="http://mathworld.wolfram.com/PrimeCountingFunction.html"]http://mathworld.wolfram.com/PrimeCountingFunction.html[/URL]), they can't actually prove all those numbers prime?[/QUOTE]

Not nearly. It takes O(log(n)^k) to test primality (3 <= k <= 12 depending on which algorithm is used), for a total time of O(n log(n)^k). That would take forever and a day for n = 10^{23}.

There are good sublinear algorithms out there, though, that make this possible as a distributed system -- but the error you point out made them stop the project.

So why was there a +-1 error?

[QUOTE=jinydu;85896]So why was there a +-1 error?[/QUOTE]

If they knew the answer to that question they would have fixed the
bug and continued the project.