# Is it possible that the formula for the $n^{th}$prime number is a polynomial in n?

I know that no pattern has been found yet. And prime numbers are weird, so the formula being a polynomial would be too simple to be true. Has there some proof been given that the expression for $n^{th}$ prime number can't be a polynomial in n?

I also found this thing on the internet that $\frac{sin^2\frac{\pi(j-1)!^2}{j}}{sin^2\frac{\pi}{j}}$ is equal to one if and only if j is prime. One thing that I got from simplifying this is that $\frac{(j-1)!^4-1}{j}$ is an integer if and only if j is prime. So, if there's some equation which is only satisfied by integers, then it will also be satisfied by $\frac{(j-1)!^4-1}{j}$ and hence it will also be satisfied by all prime numbers. Is there some equation involving continuous functions which is only satisfied by integers? I couldn't find any equation like that. It should be in terms of some standard continuous functions and shouldn't involve discontinuous functions like the greatest integer function and smallest integer function. And it shouldn't be like n%1 =0 only if n is an integer. That won't help. And also not anything like $sin(n\pi)=0$ only if n is an integer.

• No, because of the prime number theorem here: en.wikipedia.org/wiki/Prime_number_theorem – Michael Jan 22 '17 at 4:36
• Look up Wilson's theorem for why $(j-1)!+1$ is divisible by $j$ if and only if $j$ is a prime. – Thomas Andrews Jan 22 '17 at 4:47
• Using polynomials you can't do better than this – Count Iblis Jan 22 '17 at 5:37
• I disagree with your first sentence. Tens of thousands of patterns in the primes have been discovered and published in peer-reviewed journals, including (depending on how you count them) hundreds of formulas for the primes. – Charles Jan 22 '17 at 8:06
• @Dove The primes are deterministic -- 97 is always prime, no matter how often you check -- although they seem random in a sense. And there are many, many formulas for primes, including many which give the $n$-th prime. I've collected many here oeis.org/wiki/Formulas_for_primes and I have a paper in preparation with many more. – Charles Jan 22 '17 at 9:17

In fact there is no non-constant polynomial whose values at the positive integers are all primes.

First, note that any polynomial whose values at the positive integers are primes must have rational coefficients (see e.g. Integer-valued polynomials).

Suppose $P$ is such a polynomial, and let $P(x) = p$ where $p$ is coprime to the denominators of all coefficients of $x$. Then since $(x+p)^k \equiv x^k \mod p$ for all nonnegative integers $k$, we get that $P(x+p) \equiv P(x) \equiv 0\mod p$, so $P(x+p)$ can't be prime.

No, there cannot be any polynomial in $n$ whose value is always the $n$th prime.

Clearly there is no first-degree polynomial with this property. And if the polynomial has degree larger than $1$, then for large $n$ it is going to grow too fast -- such a polynomial would declare too few numbers to be primes, contradicting known facts about how common primes are, in particular the prime number theorem.

By the way, you don't need to raise to the 4th power in your primality test; Wilson's theorem says that $(n-1)!+1$ is divisible by $n$ exactly if $n$ is prime.

• So, there's no proof for that. But your argument seems fine to me. I looked up the prime number theorem. I read one thing that the probability of a number greater than N being prime is close to 1/log(N). This means that the probability tends to zero when N is large. Doesn' that mean that if an expression for the nth prime number exists, then it would also grow very fast for large n. – Dove Jan 22 '17 at 4:48
• @Dove: Not all that fast -- $p_n$ grows faster than a linear polynomial, but much slower than a quadratic one. (The theory of asymptotic growth gives a solid technical meaning to these arguments about "very fast" and "not as fast" -- there is realy no wiggle room here). – Henning Makholm Jan 22 '17 at 4:53
• @HenningMakholm what happens if we allow for complex coefficients? You can probably do the same thing using something similar to the proof of louivilles theorem – Jorge Fernández Hidalgo Jan 22 '17 at 4:56
• @JorgeFernándezHidalgo: Since we're assuming that the polynomial is real at each positive integer, it would equal its complex conjugate at those points too. But two polynomials that agree at infinitely many points are identical, so each of its coefficients equals its conjugate, so the coefficients are real. – Henning Makholm Jan 22 '17 at 5:01
• Oh, that's really cool @HenningMakholm. – Jorge Fernández Hidalgo Jan 22 '17 at 5:04

While Henning Makholm's answer is fantastic, I just feel a little uncomfortable to use so high-tech as the Prime Number Theorem.

Indeed, the reason behind the fact that no polynomial can interpolate the sequence of all primes is that there are too much primes. To be precise, we know that the primes are not an arithmetic sequence, so if a polynomial $q$ were to interpolate them it would need to have degree $\geq2$. This is key because we know that$$\sum_p\frac{1}{p}=+\infty,$$ while if $\deg q\geq2$ then we must have $$\sum_n\frac{1}{q(n)}\leq C\sum_n\frac{1}{n^2}<+\infty$$ for some constant $C$.

I can't resist the following nuke: suppose $f(x)$ is a polynomial, with leading term $a_kx^k$, such that the $n$th prime is $f(n)$. Clearly $f$ can't be linear; and now it's not hard to see that $\lim_{x\rightarrow\infty}f'(x)=\infty$, which means that we have:

For all $N$, there is some $n$ such that for all $m>n$ we have $f(m+1)-f(m)>N$.

But this is known to be false.

EDIT: Yet another nuke. It's also true that $f''$ goes to infinity (technically to conclude this we need to show that $f$ must have degree $\ge 3$, but that's not hard). So let $x$ be such that for all $y>x$, $f''(y)>0$ and $f'(y)>0$; then there are no $z>y, a>0$ such that $$f(z+a)-f(z)=f(z+2a)-f(z+a);$$ that is, there are only finitely many arithmetic sequences of length $\ge 3$ contained in the primes. But this contradicts the Green-Tao theorem: for any $n$, an arithmetic progression of length $n+2$ witnesses the fact that there are at least $n$-many length $3$ arithmetic progressions in the primes.

I do not immediately see a nuke via the third derivative of $f$.

• Oh, sweet!${}{}{}$ – Jorge Fernández Hidalgo Jan 22 '17 at 4:57
• @JorgeFernándezHidalgo I mean this is the worst possible proof, but I thought it was cute. :P (And I added another!) – Noah Schweber Jan 22 '17 at 4:58
• Interestingly, neither nuke gets the stronger result Robert Israel mentions, that no nonconstant polynomial takes on only prime values on positive integer inputs. – Noah Schweber Jan 22 '17 at 5:58