#8135: prime_pi approximation involving zeta zeros
--------------------------------------+-------------------------------------
Reporter: kevin.stueve | Owner: Kevin Stueve
Type: task | Status: new
Priority: major | Milestone:
Component: number theory | Keywords: prime counting function
Riemann zeta zeros
Author: Tomas Oliviera e Silva | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------------+-------------------------------------
Old description:
> Get an analytic approximation to prime_pi, the prime counting function
> that uses the nontrivial zeros of the Riemann zeta function.
New description:
Get into Sage an analytic approximation to prime_pi, the prime counting
function, that uses the nontrivial zeros of the Riemann zeta function.
--
Comment(by kevin.stueve):
Below is a conversation between myself and Tomas Oliviera e Silva
(Universidade de Aveiro, Portugal). I have included only the content
relevant to this ticket in particular (more of the conversation is at
[http://trac.sagemath.org/sage_trac/ticket/7013#comment:42]).
Kevin Stueve:[[BR]]
I am currently researching the error of Riemann's exact formula for
pi(x) in the form of equation 13 at
http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html. I am
contemplating various ways of compressing a table of values of the
prime counting function. Because storage cost is a major bottleneck,
even a savings of 10% or less would be worth the effort.
Are you willing to release the code you used for your estimates of the
prime counting function at http://www.ieeta.pt/~tos/primes.html#e
under a GPL compatible license?
Tomas Oliviera e Silva (TOS):[[BR]]
The equation 13 you mentioned is PROBABLY wrong: check Andrey V. Kulsha'
post of 11/18/2008 entitled "On the explicit formula for the Prime-
counting
function pi(x)" on the [email protected] list. To me, it seems
far better to compress the pi(x) data using simply pi(x)=li(x)-e(x).
Instead
of storing pi(x) you would store the (positive) value of e(x) rounded to
the
nearest integer. Note that li(x) can be computed easily and that e(x)
should
be of the order of sqrt(x). Replacing li(x) by R(x) would not help much,
because the error term could be either positive or negative (one more
bit).
Using a few zeros of the zeta function could reduce the error term, but my
experience is that it would take much more time to compute the
approximation
(it would be necessary to evaluate $li(x^rho)$ accurately, and also
pi(sqrt(x)), pi(cbrt(x)), etc.).
Kevin Stueve:[[BR]]
I am very interested in what is possible with the Riemann correction
terms. Even if they are not reasonable for use in a production prime
counting function, I would love to find a fast implementation I can
use for research (and for Sage) without implementing it myself.
Implementing it myself would be very educational (I suppose I might
start with the Gram series), but it could consume a great deal of my
time that could be spent elsewhere. Because I started out as a
computer science major, I see the problem of how much a table of
values of the prime counting function can be compressed and quickly
retrieved in theory as a problem worthy in its own right.
TOS:[[BR]]
Would you consider using the gmp and mprf packages to do the floating
point computations? I can adapt my code to compute Riemman's formula for
pi(x) using them --- it would contain calls to pi(x) itself, which I would
not implement, to compute pi(sqrt(x)), pi(cbrt(x)), etc.
Kevin Stueve:[[BR]]
Yes. I would consider using gmp and mprf. I could compute the
recursive pi(sqrt(x)) calls etc.
Tomas Oliviera e Silva:
Here goes a simple implementation of Riemann's formula in pari-gp.
Thanks Tomas! [[BR]]
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8135#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
