find Nth prime with Sage

[Szabolcs Horvát]

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?

Szabolcs

[William Stein]

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 sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> 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

[William Stein]

On Thu, Apr 3, 2014 at 11:52 AM, R. Andrew Ohana <andrew...@gmail.com> 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.

> --
> Andrew

[Andrew Ohana]

Actually you should 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).

There has been some effort to include the open source libraries primesieve and primecount in Sage which would provide a much faster Primes iterator, prime_range, prime_pi, and nth_prime, however so far these haven't made it in.

However, both of 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 (about 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.

[Szabolcs Horvát]

Than you for the responses William and Andrew.  William's idea does sound reasonable, I assumed Mathematica does something similar.  The reason I needed this functionality was actually to verify something I computed using Mathematica (for my peace of mind).  For now I will look at the primecount library, which is less work than implementing William's idea in Sage.

Szabolcs

[Dana Jacobsen]

On Wednesday, April 2, 2014 1:20:23 PM UTC-7, Szabolcs Horvát 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.

perl -MMath::Prime::Util=:all -E 'say nth_prime(10**10)'

10^10 in 0.04s
10^11 in 0.13s
10^12 in 0.81s
10^13 in 2.9s
10^14 in 13.3s

All single threaded.  Open source from CPAN or https://github.com/danaj/Math-Prime-Util

Kim's primecount uses the excellent threaded primesieve, but the nth prime is currently quite a bit slower.  MPU uses a low-biased estimate (inverse Li with small correction), uses LMO prime count, then sieves the tiny gap.  The prime count is also quite a bit faster at the moment.  Both are actively being worked on so relative times are always in flux.  I'm sure my sieving will never match his performance.

The code is all in C and C+GMP (with Math::Prime::Util::GMP).  I don't know how well any of it would mesh with SAGE, but there's lots of stuff there that would seem useful (e.g. ECPP).

Dana

[leif]

Andrew Ohana wrote:
> Actually you should 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).
>
> There has been some effort to include the open source libraries primesieve and primecount in Sage which would provide a much faster Primes iterator, prime_range, prime_pi, and nth_prime, however so far these haven't made it in.

And I just noticed that http://trac.sagemath.org/ticket/11475 is still
bit-rottening...

-leif

> However, both of 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 (about 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.

--
() The ASCII Ribbon Campaign
/\ Help Cure HTML E-Mail