Loading ...
Sorry, an error occurred while loading the content.

Re: in search of algorithm

Expand Messages
  • Luis Rodriguez
    Sorry. You are searching the impossible. Not even if the Riemann s Hypothesis is demonsrated can one reduce the error below  X^(1/2).Log(X). There is an
    Message 1 of 6 , Dec 8, 2012
    • 0 Attachment
      Sorry. You are searching the impossible. Not even if the Riemann's Hypothesis is demonsrated can one reduce the error below  X^(1/2).Log(X).
      There is an algorithm due to Riemann that gives Pi(x)  exactly, but practically is equivalent to Erathostenes because it needs to calculate the sum of all the non-trivial zeroes of Z(X).


      Ref. The Book of Prime Numbers Records (The Growth of Pi(x). Pag. 164)


      [Non-text portions of this message have been removed]
    • James Merickel
      Luis, The references I have find pi(x) faster than the sieve of Eratosthenes, and it is not that difficult to work out on one s own a means of computation
      Message 2 of 6 , Dec 8, 2012
      • 0 Attachment
        Luis,
        The references I have find pi(x) faster than the sieve of Eratosthenes, and it is not that difficult to work out on one's own a means of computation employing inclusion-exclusion. I don't have immediate access to the book referenced to see what it says exactly and don't know exactly what Riemann did with this, but it is a 19th-century result that pi(x) can be computed asymptotically faster than computing all of the primes below x. The Wikipedia article and its references (the ones I am using so far) make this clear. I suspect that the best way for me to approach this on my own is to refine what is in those references for ranges of errors versus time, but this sort of theoretical work would take me about 10 times as long as what some here could manage--probably near a month, and I was hoping that better recent references might be out there.
        Jim

        ------------------------------
        On Sat, Dec 8, 2012 7:02 AM PST Luis Rodriguez wrote:

        >Sorry. You are searching the impossible. Not even if the Riemann's Hypothesis is demonsrated can one reduce the error below  X^(1/2).Log(X).
        >There is an algorithm due to Riemann that gives Pi(x)  exactly, but practically is equivalent to Erathostenes because it needs to calculate the sum of all the non-trivial zeroes of Z(X).
        >
        >
        >Ref. The Book of Prime Numbers Records (The Growth of Pi(x). Pag. 164)
        >
        >
        >[Non-text portions of this message have been removed]
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.