1
$\begingroup$

Aside from approximation functions, are there any functions that produce an exact $n$th prime?

  • 3
    You should say what form you are prepared to accept for the function's definition, otherwise defining $p(n)$ as "the $n$th prime number" is such a function...2012-12-20

2 Answers 2

3

There are many Formulas for primes. See too MathWorld's 'Prime formulas and Rowland's paper.

For example Willans' formula : $$p_n=1+\sum_{i=1}^{\large 2^n}\left\lfloor\left(\frac n{\sum_{j=1}^i\left\lfloor\left(\cos\frac{(j-1)!+1}x\pi\right)^2\right\rfloor}\right)^{1/n}\right\rfloor$$ or Gandhi's formula : $$p_n=\left\lfloor1-\log_2\left(-\frac 12+\sum_{\large{d|P_n-1}}\frac{\mu(d)}{2^d-1}\right)\right\rfloor$$ (with $\mu$ the Möbius function)

The difficulty is to find efficient formulas (most of the previous ones are mere variations of the Wilson theorem, which means evaluating $(n-1)!\pmod{n}$ to know if $n$ is prime, or a parsing of the possible divisors up to $\sqrt{n}\,$ or $n-1$ : i.e. for one prime you need $O(n)$ or $O(\sqrt{n})$ operations).

This should be compared to the venerable sieve and more modern primality tests (with running times in $O\bigl(k\;\log(n)^m\bigr)$) as well as modern evaluation of the prime-counting function $\pi(n)$.

  • 0
    Thanks. May i ask you to elaborate on what you mean by efficient.2012-12-20
  • 0
    @Babiker: I updated my answer.2012-12-20
1

To get the $n$th prime $p_n$, you could

  1. calculate the infinite sum $$ \pi(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) $$ with $\rho$ running over all the zeros of $\zeta$ (see here)

  2. and invert the prime counting function to get $p_n=\pi^{-1}(n)$.

Ok, I'm not sure if you have the time for 1. and a way for 2.

  • 0
    +1: This analytic method was considered by Lagarias and Odlyzko in their paper ['Computing $\pi(x)$: An Analytic Method'](http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf). They considered too the method that allowed the actual evaluation of $\pi(x)$ up to $10^{23}$ : the ['Meissel-Lehmer method'](http://wstein.org/home/wstein/www/home/victor/Desktop/2007973.pdf). The latest results seem to be [here](http://primes.utm.edu/notes/pi(10%5E24).html) : up to $10^{24}$ with the analytic method! A more recent [paper](http://arxiv.org/abs/1203.5712) from Platt.2012-12-20
  • 0
    without forgetting [Galway's 2004 thesis](http://www.math.uiuc.edu/~galway/PhD_Thesis)...2012-12-20
  • 0
    @RaymondManzoni thank ou very much for the links...2012-12-20
  • 0
    Thanks @Draks: this was a kind of tribute to those who used the analytic method for fast evaluation (not really easy from my experience...).2012-12-20
  • 0
    @RaymondManzoni I just realized that it was your answer back then...2013-01-03
  • 0
    Thanks to notice @Draks ! I was always fond of this very nice formula $\displaystyle \pi(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho})$ (observing that the pole at $1$ gets a plus sign while the zeros get $-1$ shows how direct the transformation from zeros to primes really is... and allows to imagine the possibility of a simple complex counting function...).2013-01-03
  • 1
    @RaymondManzoni I love it...2013-01-03