series for $n$-th prime number and prime counting function

Question

"Theoretical Computer Science Cheat Sheet" gives the following: $$p_n = n \ln n + n \ln \ln n - n + n \frac{\ln \ln n}{\ln n} + \mathcal{O}\left( \frac{n}{\ln n}\right)$$ $$\pi (n) = \frac{n}{\ln n} + \frac{n}{(\ln n)^2} + \frac{2! n}{(\ln n)^3} +\mathcal{O} \left( \frac{n}{(\ln n)^4} \right)$$ Can anybody tell me what the pattern in these serieses are or what is the full form is?

Answer 1

So you are looking for an unknown result or for a result what just doesn't exist. Because we don't know the distribution of the gaps between the primes, that is why we don't know a formula for the $n$-th prime. You can read about this in Prime Gap wikipedia article, there are also conjectures about it.

What you found is just an approximation, that is why there is a big O at the end of the formula. You can find other approximations like this in Prime number theorem wikipedia article. Rosser's theorem could be also interesting for you, or I can offer the Prime counting function article.

There is also a good question about it in stackoverflow. One last fun fact is the connection between the distribution of prime numbers and the Riemann hypothesis. That shows us, this is really not an easy problem.

Answer 2

As mentioned in another stackoverflow answer, the formula you have for $p_n$ is a simplification of the Cipolla 1902 approximation. See Dusart 1999 page 12 or Mincu 2002. The latter has a lot of details about the formula including how to generate more terms. I've tried it, and decided it oscillates too much to be attractive with many terms. My empirical results are that m=2 plus a correctiion term related to $\left(\frac{\log\log n}{\log n}\right)^3$ works fairly well. It's not as good as the inverse Riemann R however.

For $\pi(x)$ there are many ways to compute approximations and bounds (see especially Dusart 2010, 1999, and his 1998 thesis). I'd recommend looking at the Riemann R function and its expression in terms of the logarithmic integral. This gives an extremely good approximation. If you compute the inverse of this (using a binary search, for instance), you can get an excellent approximation for $p_n$.