What's a "formula"? Is there a "formula" for the n'th prime number?

Question

Talking to some undergraduates at my university, the idea came up that there was a "formula" for the n'th square number (the formula is $n^2$) but there was no "formula" for the n'th prime number.

I raised an objection to this; I said that if "formula" just meant "algorithm which could be implemented on a computer" then of course there's a formula for the n'th prime number -- just keep factoring all numbers 2,3,4,... until you find n prime ones and then output the n'th one.

I am not particularly interested in vague informal definitions of a "formula" -- what I want to know is whether there is some well-defined standard predicate on functions from $\mathbb{N}$ to $\mathbb{N}$ -- some completely water-tight rigorous notion of what it means for a function to "have a formula", such that the function sending $n$ to the $n$th square "has a formula" but the function sending $n$ to the $n$th prime does not "have a formula". Examples of well-defined standard predicates on these functions would be things like "primitive recursive" or "recursive", however both the squaring function and the "priming function" are primitive recursive so this hierarchy is too coarse.

Is there a richer hierarchy which can somehow distinguish between these things and can somehow express the idea that "the only way to work out the n'th prime number is to just work everything out, whereas you can square a number by pressing a button on your calculator?" In some parallel universe where there was an "nth prime" button as standard on every calculator, would people think that the function sending n to the n'th prime was also "defined by a formula"?

Answer 1

I don't think there's one answer to your question. But I can think of two broad examples of formalization of "formulas".

Along the lines of your algorithmic example there is the Chomsky hierarchy which formalizes the formulas for increasingly complex levels of language. At the bottom is the class of regular expressions which are the formulas for regular languages, and at the top is the class of Turing machines which are the formulas for recursive languages (generalizing the primitive recursive languages mentioned in a comment above). There are various layers of the hierarchy in between, and there is an entire field of recursion theory which imagines extending this hierarchy above the top.

In an entirely different vein, there is the field of differential algebra, which starts with a question that has come up about about a trillion times on this site: Is there a formula for an indefinite integral of [insert favorite function here]?

Answer 2

If the Riemann Hypothesis is indeed true (most mathematicians think it is), then a very interesting class of prime number formulae will be validated. For instance, consider the expression:

$\big\lfloor A^{3^{n}}\big\rfloor$

If the RH is true, then this expression will be prime for every single positive integer $n$, for some constant $A$. This is called Mills' Constant after the man who (conditionally) proved this interesting statement, William Mills. Mathematicians have already determined the smallest such $A$, and it is approximately equivalent to 1.306377. This class of formula works for other values besides $3$, and also with ceiling functions instead of floor functions.

Another method to generate primes follows this recursion:

$a_{n}=a_{n-1}+\gcd(n,a_{n-1}) \text{ with } a_{1}=7$

This sequence is known to generate every odd prime number along with $1$, but it takes a while to do so (the largest prime in the first $10,000$ recursions is only $587$).

While not exactly a prime number generator, the polynomial $P(x) = x^{2} + x + 41$ is interesting in that for $x = 0, 1 ,2 ,3,..., 39$, it outputs a prime number. However, no polynomial will produce prime numbers for all values of $x$.

Most of this can be found on https://en.wikipedia.org/wiki/Formula_for_primes