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

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

• 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... Dec 20, 2012 at 10:52

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)$.

• Thanks. May i ask you to elaborate on what you mean by efficient. Dec 20, 2012 at 10:58
• @Babiker: I updated my answer. Dec 20, 2012 at 12:53

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.

• +1: This analytic method was considered by Lagarias and Odlyzko in their paper 'Computing $\pi(x)$: An Analytic Method'. They considered too the method that allowed the actual evaluation of $\pi(x)$ up to $10^{23}$ : the 'Meissel-Lehmer method'. The latest results seem to be here : up to $10^{24}$ with the analytic method! A more recent paper from Platt. Dec 20, 2012 at 13:56
• without forgetting Galway's 2004 thesis... Dec 20, 2012 at 14:03
• @RaymondManzoni thank ou very much for the links... Dec 20, 2012 at 14:54
• Thanks @Draks: this was a kind of tribute to those who used the analytic method for fast evaluation (not really easy from my experience...). Dec 20, 2012 at 16:36
• @RaymondManzoni I love it... Jan 3, 2013 at 21:55