6
$\begingroup$

Say you are given the $n$th prime number $p_n$, like $p_n = 85489307341$, but not $n$.

Questions:

  1. What's a quick, simple, and approximate formula for $n$?
  2. By adding more terms, can this formula be made more precise?

Edit: In reference to the answer below, how can we tweak $n = \pi(x) \approx \frac{x}{\log(x)}$ to make it more accurate?

$\endgroup$
13
  • $\begingroup$ is this really a prime number? $\endgroup$ Commented Jan 14, 2016 at 16:00
  • $\begingroup$ @Dr.SonnhardGraubner Yes. $\endgroup$
    – Wojowu
    Commented Jan 14, 2016 at 16:01
  • $\begingroup$ Many good approximations are given on wikipedia about prime number theorem $\endgroup$
    – qwr
    Commented Jan 14, 2016 at 16:06
  • $\begingroup$ One could potentially win $1 million by answering your new question, so... $\endgroup$ Commented Jan 14, 2016 at 16:34
  • $\begingroup$ @NajibIdrissi: I don't mean tweak it perfectly. I'll be happy with a slight improvement. For example, as in the link given by qwr, we have more terms as, $$\frac{p_n}{n} \approx \ln(n) + \ln\ln n - 1 $$ or better, $$\frac{p_n}{n} \approx \ln(n) + \ln\ln n - 1 +\frac{\ln\ln n - 2}{\ln n}$$ Using these, how do we isolate $n$ and express it in terms of $p_n$? $\endgroup$ Commented Jan 14, 2016 at 16:40

4 Answers 4

2
$\begingroup$
say nth_prime(3543419187)
85489307341

say prime_count(85489307341)
3543419187  # looks right

Note that prime counts at this size are quite cheap. About 19 milliseconds on my laptop. That's still over 1000x slower than the most complicated of the approximations below.

Percent difference from exact answer for various methods using this n, given in order of closeness for larger inputs:

$R(n)$ 2.3e-7 very good approximation from Riemann's R function

${\rm li}(n)-{\rm li}(n^{0.5})/2$ 1.7e-7 also very good from truncated R

${\rm li}(n)$ 3.4e-6 very good

$(\pi_{\rm upper}(n)+\pi_{\rm lower}(n))/2$ 9.5e-7 surprisingly good from average bounds, but it is all dependent on using tight bounds, and it doesn't keep up as size increases

$n/(\log(n)-1-1/\log(n))$ .00024 not horrible

$n/(\log(n)-1)$ .0019 meh

$n/\log(n)$ .042 ugh (but better than randomly guessing numbers)

$\endgroup$
2
  • 2
    $\begingroup$ Oh, come on, almost 1000 reputation points and still not formatting your posts with MathJax? $\endgroup$
    – Alex M.
    Commented Jan 14, 2016 at 21:40
  • $\begingroup$ Happier? I think the lack of tables or tabs is a bigger issue. $\endgroup$
    – DanaJ
    Commented Jan 14, 2016 at 21:58
1
$\begingroup$

For (1), you have for large $x$ that the number of primes less than or equal to $x$ is $\pi(x) \approx \frac{x}{\log(x)}$

$\endgroup$
5
  • $\begingroup$ This is a good way to put it. $\endgroup$
    – quid
    Commented Jan 14, 2016 at 16:03
  • $\begingroup$ Ah, the prime counting function $\pi(x)$. Know a way to tweak this formula to make it more sharp? $\endgroup$ Commented Jan 14, 2016 at 16:10
  • 2
    $\begingroup$ Although you never know enough in math, I think that if there were some refinement of the formula $\pi(x) \approx \frac{x}{log(X)}$ , it would be quite known. $\endgroup$
    – Piquito
    Commented Jan 14, 2016 at 16:28
  • 1
    $\begingroup$ @Piquito: $\operatorname{Li}(x)$ is much sharper than $x/\log x.$ $\endgroup$
    – Charles
    Commented Jan 14, 2016 at 20:33
  • $\begingroup$ Thank you, I have seen once about Li(x) but I have forgot it. $\endgroup$
    – Piquito
    Commented Jan 15, 2016 at 13:18
1
$\begingroup$

Much better, and given in the Wikipedia article is $$\pi(x )\approx Li(x) =\int_2^x \frac 1{\log t} \ dt$$

$\endgroup$
3
  • $\begingroup$ $$\pi(x) = 3543419187\\ \text{Li}(x) \approx 3543431315\\ \frac{x}{\ln x} \approx 3396252652$$ As in the first answer, can we add more terms to make $\text{Li}(x)$ even more accurate? $\endgroup$ Commented Jan 14, 2016 at 17:00
  • $\begingroup$ @TitoPiezasIII: Probably not. It seems that the next term is oscillatory. In any case the oscillatory component is at least $\Theta_\pm(\sqrt x)/\log^kx$ where $k$ is some constant I forgot (maybe 2). $\endgroup$
    – Charles
    Commented Jan 14, 2016 at 20:30
  • $\begingroup$ Note that $\pi(x)$ and $Li (x)$ are very close. It is known that which is higher changes infinitely many times, so the error does oscillate. $\endgroup$ Commented Jan 15, 2016 at 0:07
1
$\begingroup$

Use one of the nice approximations for $p_n / n$ in terms of $n$ (from Wikipedia's PNT entry, say) and invert it iteratively. For instance, start with $$ p_n \approx n \left(\log n + \log\log n - 1 +\frac{\log\log n - 2}{\log n}\right). $$ Initialize $n_0=p_n$. And then iterate: $$ n_{i+1}=\frac{p_n}{\log n_i + \log\log n_i - 1 + \frac{\log\log n_i - 2}{\log n_i}}. $$ This converges nicely if $p_n$ is large... in your case I find $n\approx 3.5431\times 10^9$, which differs from the exact answer of $n=3543419187$ by about $0.01\%$.

$\endgroup$
1
  • $\begingroup$ This is quite indirect. The approach via the prime counting function seems superior. $\endgroup$
    – quid
    Commented Jan 14, 2016 at 22:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .