13
$\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
    $\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$ – Will Orrick Mar 22 '15 at 18:28
  • 4
    $\begingroup$ If he was "rewarded"? $\endgroup$ – anomaly Mar 22 '15 at 20:33
  • 1
    $\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 '15 at 7:33
  • 3
    $\begingroup$ If "he" was rewarded? $\endgroup$ – Eli Rose -- REINSTATE MONICA Mar 23 '15 at 9:29
  • 1
    $\begingroup$ It is not elementary functions. $\endgroup$ – Anixx Mar 23 '15 at 13:40
13
$\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$
16
$\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$
  • 1
    $\begingroup$ This is more like a computer program rather than a closed-form formula... $\endgroup$ – user541686 Mar 23 '15 at 9:44
  • 3
    $\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$ – barak manos Mar 23 '15 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 '15 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$ – barak manos Mar 23 '15 at 9:58
  • $\begingroup$ How about nice = elementary? $\endgroup$ – user541686 Mar 23 '15 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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