On Thu, Apr 3, 2014 at 11:52 AM, R. Andrew Ohana <[email protected]> wrote: > Actually you only need the RH to prove that this method is reasonably fast. > I don't think sage has Li^{-1} implemented, which is really what you need in > order to implement this ( Li ~ pi, so Li^{-1} ~ pi^{-1} = nth_prime > function).
Yes, but you can reasonably efficiently iteratively compute Li inverse, since Li is numerical and fast to compute explicitly... > There has been some effort to include the open source libraries primesieve > and primecount in Sage which would prime a much faster Primes iterator, > prime_range, prime_pi, and nth_prime, however so far these haven't made it > in. > > These libraries do have a command line interface, and depending on the > platform you are using there might be a precompiled binary. See > primesieve.org and github.com/kimwalisch/primecount. The primecount library > is much newer (less than a year old), and a lot of performance improvements > are still being made to it, but currently its nth_prime functionality takes > around half a second for input around 10^10. > > > On Thu, Apr 3, 2014 at 11:14 AM, William Stein <[email protected]> wrote: >> >> On Wed, Apr 2, 2014 at 1:20 PM, Szabolcs Horvát <[email protected]> >> wrote: >> > Hello, >> > >> > I'm quite new to Sage. Does it have any functionality that will easily >> > compute the Nth prime and it's fast enough that it will work for N of the >> > order 10^9 or 10^10 reasonable quickly (say, under 10 seconds)? >> > >> > pari.nth_prime(1000000000) takes a very long time. >> > >> > Are there alternatives? >> >> You could get an estimate for an x such pi(x) ~ N using Li(x) (and of >> course assuming RH). >> Then use prime_pi in Sage, which is vastly faster than nth_prime to >> iteratively adjust x until you find N or something close -- once >> close, just start doing primality testing which is fast around this >> range. >> In the range where pari.nth_prime is taking 20-30 seconds, prime_pi is >> much, must faster, so >> this might work. >> >> The above strategy isn't implemented. You'll have to implement it. >> I'm not sure if it works well or not, but it is what I would do. It >> should be easy to implement, and you should submit the result for >> inclusion in sage. >> >> By the way, prime_pi is faster than pari because it is >> Cython-code-from-scratch that Andrew Ohana wrote for Sage as part of >> an undergrad student project. It is not asymptotically the fastest, >> but in the range you care about it is useful. >> >> William >> >> > >> > Szabolcs >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "sage-support" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> > an email to [email protected]. >> > To post to this group, send email to [email protected]. >> > Visit this group at http://groups.google.com/group/sage-support. >> > For more options, visit https://groups.google.com/d/optout. >> >> >> >> -- >> William Stein >> Professor of Mathematics >> University of Washington >> http://wstein.org > > > > > -- > Andrew -- William Stein Professor of Mathematics University of Washington http://wstein.org -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
