1
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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... $\endgroup$
    – AakashM
    Dec 20, 2012 at 10:52

2 Answers 2

3
$\begingroup$

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

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

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.

$\endgroup$
7
  • $\begingroup$ +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. $\endgroup$ Dec 20, 2012 at 13:56
  • $\begingroup$ without forgetting Galway's 2004 thesis... $\endgroup$ Dec 20, 2012 at 14:03
  • $\begingroup$ @RaymondManzoni thank ou very much for the links... $\endgroup$
    – draks ...
    Dec 20, 2012 at 14:54
  • $\begingroup$ Thanks @Draks: this was a kind of tribute to those who used the analytic method for fast evaluation (not really easy from my experience...). $\endgroup$ Dec 20, 2012 at 16:36
  • 1
    $\begingroup$ @RaymondManzoni I love it... $\endgroup$
    – draks ...
    Jan 3, 2013 at 21:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .