mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2006-01-12, 15:39   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,253 Posts
Default 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?
ATH is offline   Reply With Quote
Old 2006-01-18, 04:31   #2
maxal
 
maxal's Avatar
 
Feb 2005

111111012 Posts
Default

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
maxal is offline   Reply With Quote
Old 2006-08-30, 04:02   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2006-08-30, 04:26   #4
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

6DE16 Posts
Default

So why was there a +-1 error?
jinydu is offline   Reply With Quote
Old 2006-08-30, 17:59   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jinydu View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Special project #3b - Project 400 schickel Aliquot Sequences 307 2011-10-28 01:29
Special project #3a - Project 300 schickel Aliquot Sequences 29 2011-08-12 17:45
Possible new project for RPS robert44444uk Riesel Prime Search 1 2010-04-30 22:01
psp-project.de down opyrt Prime Sierpinski Project 6 2010-04-20 10:51
new project 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔