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
  • 5
    $\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
  • 6
    $\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$

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.