#7013: [with patch, needs work] prime_pi and nth_prime
-----------------------------+----------------------------------------------
Reporter: kevin.stueve | Owner: kevin.stueve
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.1
Component: number theory | Keywords: primes, sieve, table,LMO
Work_issues: | Author: Kevin Stueve
Upstream: N/A | Reviewer: was,robertwb,GeorgSWeber
Merged: |
-----------------------------+----------------------------------------------
Comment(by kevin.stueve):
I would suggest using an approximation to R(x), the Riemann prime counting
function described at
http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html, if a fast
approximation (R_approx()) can be written (perhaps a Taylor or asymptotic
series?), and li_approx otherwise. The 10% or so storage savings should
be worthwhile, especially if larger tables will become available.
Alternatively, some sort of a piecewise shifted li_approx fit could be
used (meaning we start with li_approx and shift it by a pre-calculated
amount in different intervals), probably obtaining accuracy similar to R()
or R_approx(). I agree with the always 32 bit suggestion, as this should
not affect the compression considerably, and will make the code simpler.
Another space optimization to consider, especially with denser tables, is
storing the number of primes in an interval (or the offset from an
estimate of this from Li() or R()) instead of the prime counting function.
This may also save 10% or so in storage. Storing the number of primes in
bins is what Andrew Booker does on the UTM "nth prime page".[[BR]]
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:38>
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.
