mersenneforum.org pi(x) project
 Register FAQ Search Today's Posts Mark Forums Read

 2006-01-12, 15:39 #1 ATH Einyen     Dec 2003 Denmark 3,253 Posts pi(x) project I found this pi(x) project 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 (http://mathworld.wolfram.com/PrimeCountingFunction.html), they can't actually prove all those numbers prime? Anyone continuing pi(x) above 10^23?
2006-01-18, 04:31   #2
maxal

Feb 2005

111111012 Posts

From SeqFan:
Quote:
 Originally Posted by 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... http://www.ams.org/journal-getitem?p...718-96-00674-6 http://citeseer.nj.nec.com/8559.html http://numbers.computation.free.fr/C...constants.html and Marc Deléglise habilitation On the Lagarias-Odlyzko algorithm: http://www.math.uiuc.edu/~galway/Sli...-slides-98.pdf http://www.math.uiuc.edu/~galway/Sli...lides-98.ps.gz ralf

2006-08-30, 04:02   #3
CRGreathouse

Aug 2006

135338 Posts

Quote:
 Originally Posted by ATH 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 (http://mathworld.wolfram.com/PrimeCountingFunction.html), they can't actually prove all those numbers prime?
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.

 2006-08-30, 04:26 #4 jinydu     Dec 2003 Hopefully Near M48 6DE16 Posts So why was there a +-1 error?
2006-08-30, 17:59   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by jinydu So why was there a +-1 error?
If they knew the answer to that question they would have fixed the
bug and continued the project.

 Similar Threads Thread Thread Starter Forum Replies Last Post schickel Aliquot Sequences 307 2011-10-28 01:29 schickel Aliquot Sequences 29 2011-08-12 17:45 robert44444uk Riesel Prime Search 1 2010-04-30 22:01 opyrt Prime Sierpinski Project 6 2010-04-20 10:51 junky NFSNET Discussion 18 2004-03-08 03:05

All times are UTC. The time now is 23:58.

Sat Jan 22 23:58:32 UTC 2022 up 183 days, 18:27, 0 users, load averages: 1.30, 1.29, 1.16