We know by the prime number theorem that $\lim_{n\to\infty}\frac{\pi(n)}{n\,/\ln n} = 1$ An even better approximation is $\lim_{n\to\infty}\frac{\pi(n)}{\int_2^n\frac{1}{\ln t}\mathrm{d}t} = 1$.

Is there a similar formula that approximates the distribution of natural numbers of the form $p^n$ where $p$ is a prime? That is, an approximation of $$\pi'(x)=\left|\,\Pi'\cap\{1,\ldots,x\}\,\right| \qquad\mbox{ where }\quad \Pi'=\{p^n\;|\;p\mbox{ is prime}, n\in\mathbb{N}\}$$

(There is already a question that asks if $\lim_{n\to\infty}\frac{\pi'(n)}{n}=0$, but I'm interested in a more precise approximation.)

  • 3
    $\begingroup$ Note that $\pi'(x)=\pi(x)+\pi(x^{1/2})+\pi(x^{1/3})+\pi(x^{1/4})+\cdots$ $\endgroup$ – anon May 19 '13 at 20:10
  • $\begingroup$ is that really elementary number theory! btw I wonder if there's any reason for using both $\ln$ and $\log$. $\endgroup$ – user59671 May 19 '13 at 22:41
  • $\begingroup$ @CutieKrait $\ln$/$\log$ was a mistake, fixed. Do you have a suggestion for a better tag? $\endgroup$ – Petr May 20 '13 at 5:40
  • $\begingroup$ @PetrPudlák: in analytic number theory, $\log$ is usually used for $\ln$; no idea why. However in calculus and outside pure math, $\log$ is supposed to have base 10. there's a "number-theory" tag too which is different from "elementary number theory". $\endgroup$ – user59671 May 20 '13 at 9:45

The same asymptotics hold, and the intuitive explanation for that is that the number of prime powers up to $x$ are negligible in comparison to the number of primes up to $x$. In fact, the usual proofs of the prime number theorem actually prove the asymptotics for $\pi'$ first, and then one shows that these coincide with the asymptotics of $\pi$.

Since $\pi'(x)$ for a real $x$ counts the number of primes $p$ up to $x$, the number of prime squares $p^2$ up to $x$, the number of prime cubes $p^3$ up to $x$, and so on, we can write $$\pi'(x)=\pi(x)+\pi(x^{1/2})+\pi(x^{1/3})+\cdots+\pi(x^{1/m})$$ where $m=\log(x)+1$. Now, using the prime number theorem, we get $$\pi'(x)-\pi(x)\sim x^{1/2}/\log(x^{1/2})+\cdots+x^{1/m}/\log(x^{1/m})$$ which can be bounded above by $x^{1/2}/\log(x^{1/2})\cdot (\log x+1)\leq x^{1/2}/\log(x^{1/2})\cdot 2\log x=4 x^{1/2},$ and thus $\pi'(x)=\pi(x)+O(x^{1/2})$, so $\pi'(x)$ is asymptotic to $x/\log x$.

  • $\begingroup$ Where is the log(x)+1 derived from? $\endgroup$ – Stephen Nov 14 '16 at 17:58
  • 1
    $\begingroup$ @Lucas: I'm just taking $m$ large enough such that $x^{1/m}$ is smaller than 2. I see now that taking $m=\log x/\log 2$ would've made more sense. $\endgroup$ – Samuel Nov 15 '16 at 7:44

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.