= Solution
Write $\vartheta(x)=\sum_{p\le x}\log p$ and $\psi(x)=\sum_{n\le x}\Lambda(n)$ for the two <Chebyshev functions>, and $\pi(x)$ for the <prime-counting function>. If $m<p\le2m$, the <prime> $p$ divides the central <binomial coefficient> $\binom{2m}{m}$. Consequently
$$
\vartheta(2m)-\vartheta(m)\le\log\binom{2m}{m}\le2m\log2.
$$
Sum this inequality over dyadic integers $m=1,2,4,\ldots,2^{k-1}$. It gives $\vartheta(2^k)\le2^{k+1}\log2$. <Monotonicity>, with $2^{k-1}<x\le2^k$, gives $\vartheta(x)=O(x)$ for real $x\ge2$. This is the <Chebyshev estimate from central binomial coefficients>; no information about the distribution of <primes> beyond <unique factorization> has been used.
Split the <primes> at $\sqrt x$. For $p>\sqrt x$, $\log p>\tfrac12\log x$, so
$$
\pi(x)\le\sqrt x+\frac{2\vartheta(x)}{\log x}.
$$
Since $\sqrt x=O(x/\log x)$,
$$
\boxed{\pi(x)=O\left(\frac{x}{\log x}\right).}
$$
We also need $\psi(x)=O(x)$. The contributions of higher <prime powers> satisfy
$$
\psi(x)=\sum_{k\ge1}\vartheta(x^{1/k})=\vartheta(x)+O(\sqrt x\log x)=O(x),
$$
because only $k\le\log x/\log2$ contribute, and $\vartheta(x^{1/k})\ll\sqrt x$ for $k\ge2$.
The <Von Mangoldt divisor identity> is $\log n=\sum_{d\mid n}\Lambda(d)$, which follows by factoring $n$ into <prime powers>. Summing it for $n\le M$, with $M$ a positive integer, gives
$$
\log(M!)=\sum_{d\le M}\Lambda(d)\left\lfloor\frac Md\right\rfloor
=M\sum_{d\le M}\frac{\Lambda(d)}d+O(\psi(M)).
$$
The bound already proved makes the last error $O(M)$. Integral comparison for $\sum_{n\le M}\log n$, or the <Stirling formula>, gives $\log(M!)=M\log M-M+O(\log M)$. Therefore
$$
\sum_{d\le M}\frac{\Lambda(d)}d=\log M+O(1).
$$
The contribution from higher <prime powers> is uniformly bounded:
$$
\sum_p\sum_{k\ge2}\frac{\log p}{p^k}=\sum_p\frac{\log p}{p(p-1)}\le\sum_{n\ge2}\frac{\log n}{n(n-1)}<\infty.
$$
Subtract it, and replace $M$ by $\lfloor x\rfloor$, to obtain the <Mertens first theorem>
$$
\boxed{A(x):=\sum_{p\le x}\frac{\log p}{p}=\log x+O(1).}
$$
Now fix $\delta>0$. Apply <partial summation> to $A(t)$ and $f(t)=(\log t)^{-1-\delta}$. With the lower endpoint interpreted as $2^-$, so that the <prime> $2$ is included, this gives
$$
\sum_{p\le x}\frac1{p(\log p)^\delta}
=\frac{A(x)}{(\log x)^{1+\delta}}+(1+\delta)\int_2^x\frac{A(t)}{t(\log t)^{2+\delta}}\,dt.
$$
The boundary term tends to zero, and the integral converges, since $A(t)\ll\log t$ and $\int_2^\infty dt/(t(\log t)^{1+\delta})<\infty$. Thus \b[the series converges for every positive $\delta$]. Keeping the main term of $A(t)$ also gives the useful <logarithmically weighted reciprocal-prime tail>
$$
\boxed{\sum_{p>x}\frac1{p(\log p)^\delta}=\frac1{\delta(\log x)^\delta}+O_\delta\left(\frac1{(\log x)^{1+\delta}}\right).}
$$
Indeed, subtract the finite partial sum from the limiting integral: the boundary contributes $-(\log x)^{-\delta}$ and the main integral contributes $(1+\delta)(\log x)^{-\delta}/\delta$.
Back to article page
