14
$\begingroup$

I just found out on Wolfram that there is a formula for the n-th prime in terms of elementary functions. I wonder who found it and if he was rewarded for this. The formula (here) is:

enter image description here

Also shown at http://www.wolframalpha.com/input/?i=prime(n)

$\endgroup$
6
  • 7
    $\begingroup$ This question is relevant. The answer of Dan Petersen, in particular, contains a link to a nice article by Underwood Dudley that contains some history. $\endgroup$ Mar 22, 2015 at 18:28
  • 6
    $\begingroup$ If he was "rewarded"? $\endgroup$
    – anomaly
    Mar 22, 2015 at 20:33
  • 2
    $\begingroup$ The formula here doesn't actually give any insight into computing the $n$th prime efficiently, all it does is encode (obfuscate?) the process of trial division, or something related, into an unreadable mathematical expression. The presence of floor operations and sums (which are a cute but in this context uninteresting way to emulate conditionals and loops) give it away. $\endgroup$
    – Thomas
    Mar 23, 2015 at 7:33
  • 7
    $\begingroup$ If "he" was rewarded? $\endgroup$
    – Eli Rose
    Mar 23, 2015 at 9:29
  • 2
    $\begingroup$ It is not elementary functions. $\endgroup$
    – Anixx
    Mar 23, 2015 at 13:40

2 Answers 2

19
$\begingroup$

Here is something that I have established a long time ago. It doesn't answer your question directly, but rather illustrates the fact that one can easily establish such formula (the one below is given by $P_n$). The real challenge is to establish a prime-formula which is not "computationally worthless".


Is $n$ prime:

$$F_n=\left\lfloor\frac{\left(\sum\limits_{k=2}^{n-1}\left\lceil\frac{{n}\bmod{k}}{n}\right\rceil\right)+2\cdot\left\lceil\frac{n-1}{n}\right\rceil}{n}\right\rfloor$$


How many primes until $n$:

$$G_n=\sum\limits_{k=2}^{n}F_k$$


What is the $n$th prime number:

$$P_n=\sum\limits_{k=n}^{n^2+1}{k}\cdot{F_k}\cdot\left(1-\left\lceil\frac{(G_k-n)^2}{(G_k+n)^2}\right\rceil\right)$$

$\endgroup$
7
  • 1
    $\begingroup$ This is more like a computer program rather than a closed-form formula... $\endgroup$
    – user541686
    Mar 23, 2015 at 9:44
  • 4
    $\begingroup$ @Mehrdad: That is precisely what I was implying at the beginning (top part) of the answer. BTW, I'm not sure that there even exists a definition that accurately distinguishes between a computer program and a closed-form formula (i.e., every computer program can be converted into a formula and vice-versa). $\endgroup$ Mar 23, 2015 at 9:46
  • $\begingroup$ I mean, it would be a lot cooler if you could do the same thing in terms of mathematically "nice" functions (e.g. perhaps smoother... no floors/ceilings/absolute values/etc.). And yeah, I don't think there's a rigorous distinction between the two... it's an "I know it when I see it" kind of thing. $\endgroup$
    – user541686
    Mar 23, 2015 at 9:54
  • $\begingroup$ @Mehrdad: Yep. And in addition to that, unless you can provide a mathematical definition of the term "nice", it remains subjected to personal perspective. $\endgroup$ Mar 23, 2015 at 9:58
  • $\begingroup$ How about nice = elementary? $\endgroup$
    – user541686
    Mar 23, 2015 at 10:00
18
$\begingroup$

There are many formulas for the $n$th prime. The only really useful ones are in the form of fast computer programs (yes, those are formulas too, just not what you would normally consider a "closed-form" formula of elementary functions).

Consider the formula in question here,

enter image description here

Observe that in order to find the $n$th prime, this formula requires you to compute $2^n$ terms of the sum. Hence as an algorithm it is of order $\Omega(2^n)$, which is pretty bad.

In addition to the question The myth of no prime formula? already cited in a comment, see the following

$\endgroup$

You must log in to answer this question.

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