$\pi(x)$ is defined as number of primes less than or equal to x. Gauss showed that $\pi(x) \approx \frac{x}{log(x)}$. I want to calculate the inverse of that approximation because I want to estimate how far should I sieve in order to get the number of primes that I want. Here are the steps that I took.

$$\begin{align}y &= \frac{x}{\log(x)}\\ x &= y \log(x) \\ e^x&=e^{y\log(x)} \\ e^x &= (e^{\log(x)})^y \\ e^x &= x^y\end{align}$$

I am stuck at this point. How can I calculate $y$ in terms of $x$?

  • 2
    For an exact formula, use the Lambert W function, but in your case a numerical method like Newton's method will do. – Jean-Claude Arbaut Aug 6 at 20:46
  • 1
    I believe you can't do it analytically. – fonini Aug 6 at 20:46

Resorting to Lambert's $W$ is a little overkill.

With $$x=y\ln y,$$ we have

$$\frac x{\log x}=\frac{y\ln y}{\ln(y\ln y)}=\frac{y\ln y}{\ln y+\ln\ln y}\approx y.$$

Given that the distribution is anyway approximate, this can be a sufficient approximation of the inverse. Or you can use it as a starting value for Newton's iterations (use few of them anyway).

  • $x = y / \ln y$ I think? division not multiplication? – Claude Aug 6 at 20:53
  • 1
    @Claude: the problem statement says $y=x/\log x$, then $x\approx y\log y$. – Yves Daoust Aug 6 at 20:54
  • oh, I see now what you are doing – Claude Aug 6 at 20:56
  • 1
    @yasar Try to plug it: set $x := y\ln y$. Then $$\frac{x}{\ln x} = \frac{y\ln y}{\ln(y\ln y))} = \frac{y\ln y}{\ln y + \ln\ln y} = \frac{y}{1+\frac{\ln\ln y}{\ln y}} = y - y\frac{\ln\ln y}{\ln y} + o\left(y\frac{\ln\ln y}{\ln y} \right) = y + o(y)$$ – Clement C. Aug 6 at 21:16
  • 1
    @ClementC. Indeed, but it does work here: it is known that $n (\log n + \log \log n - 1) < p(n) < n (\log n + \log \log n)$ for $n \ge 6$. – Robert Israel Aug 7 at 4:50

To be clear about what is hinted at in the comments, $$ f^{-1}(y) = -y\,W(-\tfrac{1}{y}) $$ where $W$ is the Lambert-$W$ function. (You can verify this in Mathematica.) If you wanted an asymptotic expansion check the wiki article and plug one in.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.