## in search of algorithm

Expand Messages
• Hello, group members. To a degree, I am able to locate and work with what I am interested in, but perhaps somebody can facilitate my efforts either with
Message 1 of 6 , Dec 8, 2012
Hello, group members.
To a degree, I am able to locate and work with what I am interested in, but perhaps somebody can facilitate my efforts either with reference or a re-working of something out there to something a little closer to what I want than what is available. What I would like is an algorithm that will approximate, not compute precisely, the pi (prime counting) function to within its squareroot or somewhat less. I'll hold back exactly what I want this for for the time being.
Thanks if you can assist.
James G. Merickel
• The logarithmic integral and the Riemann approximation should get you within the square root of pi(x). I did not check if this is provenly so, but it works
Message 2 of 6 , Dec 8, 2012
The logarithmic integral and the Riemann approximation should get you within the square root of pi(x). I did not check if this is provenly so, but it works for the numbers I play with. There are even better approximations using a lot of zeros of the Riemann zea function. Look at the prime-counting function in Wikipedia.

- David

--- In primenumbers@yahoogroups.com, James Merickel <moralforce120@...> wrote:
>
>
> Hello, group members.
> To a degree, I am able to locate and work with what I am interested in, but perhaps somebody can facilitate my efforts either with reference or a re-working of something out there to something a little closer to what I want than what is available. What I would like is an algorithm that will approximate, not compute precisely, the pi (prime counting) function to within its squareroot or somewhat less. I'll hold back exactly what I want this for for the time being.
> Thanks if you can assist.
> James G. Merickel
>
• David: Well, I have details of the kind for getting the value exactly (though it may not be the clearest thing to read or implement in something akin to te way
Message 3 of 6 , Dec 8, 2012
David:
Well, I have details of the kind for getting the value exactly (though it may not be the clearest thing to read or implement in something akin to te way I want). I guess what I am asking for and would be clearer if I stated why. Would like not-already-known palprimes w. palindrome index, in as fast a calculation as possible. Palindromic index can be ruled out with approximation about the accuracy I am saying, regularly (not always). Calculating too sharply is slow.
I appreciate the suggestion. Already past that stage myself, though.
JGM
------------------------------
On Sat, Dec 8, 2012 2:52 AM PST pbtoau wrote:

>The logarithmic integral and the Riemann approximation should get you within the square root of pi(x). I did not check if this is provenly so, but it works for the numbers I play with. There are even better approximations using a lot of zeros of the Riemann zea function. Look at the prime-counting function in Wikipedia.
>
>- David
>
>--- In primenumbers@yahoogroups.com, James Merickel <moralforce120@...> wrote:
>>
>>
>> Hello, group members.
>> To a degree, I am able to locate and work with what I am interested in, but perhaps somebody can facilitate my efforts either with reference or a re-working of something out there to something a little closer to what I want than what is available. What I would like is an algorithm that will approximate, not compute precisely, the pi (prime counting) function to within its squareroot or somewhat less. I'll hold back exactly what I want this for for the time being.
>> Thanks if you can assist.
>> James G. Merickel
>>
>
>
• David: Well, I have details of the kind for getting the value exactly (though it may not be the clearest thing to read or implement in something akin to te way
Message 4 of 6 , Dec 8, 2012
David:
Well, I have details of the kind for getting the value exactly (though it may not be the clearest thing to read or implement in something akin to te way I want). I guess what I am asking for and would be clearer if I stated why. Would like not-already-known palprimes w. palindrome index, in as fast a calculation as possible. Palindromic index can be ruled out with approximation about the accuracy I am saying, regularly (not always). Calculating too sharply is slow.
I appreciate the suggestion. Already past that stage myself, though.
JGM
------------------------------
On Sat, Dec 8, 2012 2:52 AM PST pbtoau wrote:

>The logarithmic integral and the Riemann approximation should get you within the square root of pi(x). I did not check if this is provenly so, but it works for the numbers I play with. There are even better approximations using a lot of zeros of the Riemann zea function. Look at the prime-counting function in Wikipedia.
>
>- David
>
>--- In primenumbers@yahoogroups.com, James Merickel <moralforce120@...> wrote:
>>
>>
>> Hello, group members.
>> To a degree, I am able to locate and work with what I am interested in, but perhaps somebody can facilitate my efforts either with reference or a re-working of something out there to something a little closer to what I want than what is available. What I would like is an algorithm that will approximate, not compute precisely, the pi (prime counting) function to within its squareroot or somewhat less. I'll hold back exactly what I want this for for the time being.
>> Thanks if you can assist.
>> James G. Merickel
>>
>
>
• 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 5 of 6 , Dec 8, 2012
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]
• 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 6 of 6 , Dec 8, 2012
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.