Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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... –  AakashM Dec 20 '12 at 10:52

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks. May i ask you to elaborate on what you mean by efficient. –  Babiker Dec 20 '12 at 10:58
    
@Babiker: I updated my answer. –  Raymond Manzoni Dec 20 '12 at 12:53
    
+1 for a nice collection of links.. –  draks ... Dec 20 '12 at 16:27

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.

share|improve this answer
    
+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. –  Raymond Manzoni Dec 20 '12 at 13:56
    
without forgetting Galway's 2004 thesis... –  Raymond Manzoni Dec 20 '12 at 14:03
    
@RaymondManzoni thank ou very much for the links... –  draks ... Dec 20 '12 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...). –  Raymond Manzoni Dec 20 '12 at 16:36
1  
@RaymondManzoni I love it... –  draks ... Jan 3 '13 at 21:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.