-1
$\begingroup$

By Prime Number theorem $\pi(x)=\frac{x}{\log{x}}$ for large x

Putting $x=p_n$ where $p_n$ denotes $n^{th}$ prime number,
We have, $\pi(p_n)=\frac{p_n}{\log{p_n}}$,
$\because \pi(p_n)=n$,
$\therefore \frac{p_n}{\log{p_n}}=n$,
$\therefore p_n=\pi^{-1}(n)$,
Thus, finding inverse of $y=\frac{x}{\log{x}}$ would help us to find $n^{th}$ prime number for large $n$
Please provide clues to find it?

$\endgroup$
  • 1
    $\begingroup$ Since this cannot be done in elementary way, a special function called Lambert W-function is introduced for this kind of needs. $\endgroup$ – Sangchul Lee Mar 28 at 17:11
  • 1
    $\begingroup$ Well, it's not fatal: it is invertible for a generous range of positive $x$s (very likely $x >e$), which is all you need anyway. (Hence my deletion, since my comment is a bit irrelevant.) $\endgroup$ – Randall Mar 28 at 17:12
  • 1
    $\begingroup$ Oh, I didn't say you could write it down in closed form. Just as if I asked you for the inverse of $\sin x$ on a suitable domain, you can't say anything better than $\arcsin x$. $\endgroup$ – Randall Mar 28 at 17:14
  • 7
    $\begingroup$ The Prime Number Theorem does not say $\pi(x) = \frac{x}{\log x}$ for large $x$; it only says their ratio approaches $1$. Their difference can be arbitrarily large. See OEIS sequence A057835. $\endgroup$ – FredH Mar 28 at 17:16
  • 1
    $\begingroup$ @mathaholic In closed form without a decimal approximation? I doubt it. $\endgroup$ – Randall Mar 28 at 17:17
2
$\begingroup$

I don't know about prime numbers, but the easiest way to find the inverse is usually to use substitution:

$$\pi(x)=\frac{x}{\log{x}}\land u=\pi^{-1}(x)\implies x=\frac{u}{\log{u}}$$

$$\implies x\log{u}=u\implies u^x=e^u\implies u=-xW_{-1}\left(-\frac{1}{x}\right)$$

(there's a step between $u^x=e^u$ and $u=-xW(-1/x)$ that I skipped, but I would never do it by hand anyway.)

Where $W$ is the product-logarithm or Lambert W function, as it is also called. $W$ and $W_{-1}$ are both built into Wolfram Alpha, so for particular values, I would just enter it there.

You can input it as -x ProductLog(-1,-1/x).

$\endgroup$
  • $\begingroup$ Just a nitpicking: The standard branch cut, i.e. $W = W_0$, is not adequate for OP's question since $$\lim_{x\to\infty} \frac{W(-1/x)}{-1/x} = 1.$$ You may want to use the other branch cut $W_{-1}$. $\endgroup$ – Sangchul Lee Mar 28 at 17:29
  • $\begingroup$ @SangchulLee Fair enough. Normally I would just treat everything as set-valued and call it a day. $\endgroup$ – R. Burton Mar 28 at 17:32
2
$\begingroup$

An asymptotically correct inverse of $\frac{x}{\log x}$ is $x \log x$. It has been shown by Rosser that $n\log n$ is always an underestimate for the $n$th prime. Better estimates, due to Rosser and Dusart, show that the $n$th prime lies between $$ n(\log n + \log\log n - 1) $$ and $$ n(\log n + \log\log n) $$ for all $n\ge 6$.

For example, taking $n = 10^6$, this shows that the millionth prime is between $15441302$ and $16441302$. In fact, it is nearer the lower value: $p_{1000000} = 15485863$.

$\endgroup$
1
$\begingroup$

Apart from the solution of $y=x/\log(x)$ in terms of the Lambert $W$ function, you can also solve it numerically by the simple iterative procedure

$$ x_{n}= y \log(x_{n-1})$$

with $x_0 = y \log(y)$. It converges fast, especially for large $n$.

$\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.