How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$? I saw reference to this result of Chebyshev's:
$$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty,$$
and its relation to the Prime Number Theorem. I'm looking into an information-theory proof by Kontoyiannis I was wondering if anyone could give me a sense for how difficult or involved the usual proof is.
I don't really need to see the whole thing in detail, more wondering about the general difficulty/complexity of the result. Thanks!
 A: This proof differs from the others in that it uses the prime number theorem with remainder term, which is perhaps overpowered for this, but gives a somewhat shorter proof.
Using Riemann-Stieltjes integration, the sum can be written as
$$
\sum_{p \leq x} {\log p \over p}
 = \sum_{n \leq x} {\log n \over n} \Big\{{\pi(n) - \pi(n-1)}\Big\}
 = \int_2^x {\log t \over t} d\pi(t),
$$
and using integration by parts gives
$$
\sum_{p \leq x} {\log p \over p}
 = {{\log t \over t} \pi(t)}\Bigg|_2^x - \int_2^x {1 - \log t \over t^2} \pi(t) dt. \tag{1}
$$
Using the simplest form of the prime number theorem, $\pi(x) \sim x/\log x$, we see that the evaluated terms before the integral are $O(1)$ as $x \to \infty$. To handle the integral itself, we will use the prime number theorem in the form
$$
\pi(x) = \operatorname{li}(x) + O\Big({x e^{-c\sqrt{\log x}}}\Big), \tag{2}
$$
together with an expansion of $\operatorname{li}(x)$. Integrating by parts twice, we have
\begin{align*}
\operatorname{li}(x)
 &= \operatorname{li}(2) + \int_2^x {dt \over \log t}
 = \operatorname{li}(2) + \bigg\{{{t \over \log t}}\bigg|_2^x + \int_2^x {dt \over \log^2 t}\bigg\} \\
 &= {x \over \log x}
  + \bigg\{{{t \over \log^2 t}}\bigg|_2^x + 2\int_2^x {dt \over \log^3 t}\bigg\} + O(1) \\
 &= {x \over \log x} + {x \over \log^2 x}
  + O\bigg({{x \over \log^3 x}}\bigg).
\end{align*}
The error term in (2) can be subsumed by this error term, and so the integral in (1) is
\begin{align*}
\int_2^x {1 - \log t \over t^2} \pi(t) dt
 &= \int_2^x {1-\log t \over t^2}
  \bigg\{{t \over \log t} + {t \over \log^2 t}
   + O\bigg({t \over \log^3 t}\bigg) \bigg\} dt \\
 &= \int_2^x \bigg\{{1 \over t \log t}
   + {1 \over t \log^2 t}
   + O\bigg({1 \over t \log^3 t}\bigg) \bigg\} dt \\
  &\qquad- \int_2^x \bigg\{{{1 \over t}
   + {1 \over t \log t}
   + O\bigg({1 \over t \log^2 t}}\bigg)\bigg\} dt,
\end{align*}
which can be directly evaluated by the fundamental theorem of calculus as
\begin{align*}
 &= \log \log x - {1 \over \log x} - O\bigg({{1 \over 2 \log^2 x}}\bigg)
  - \log x - \log \log x + O\bigg({1 \over \log x} \bigg) \\
 &= -\log x + O(1).
\end{align*}
Plugging this back into (1) gives the desired result.
A: The result is fairly elementary.  Lets prove it now:
Recall some common definitions: Let $\theta(x)=\sum_{p\leq x} \log p$, let $\Lambda(n)$ be the Von Mangoldt lambda function and let $\psi(x)=\sum_{n\leq x} \Lambda(n)$ 
Then as $\log n =\sum_{d|n} \Lambda(n)$ we see that $$\sum_{n\leq x} \log n=\sum_{n\leq x}\sum_{d|n} \Lambda(d)=\sum_{d\leq x} \Lambda(d)\lfloor x/d\rfloor =x\sum_{d\leq x} \frac{\Lambda(d)}{d}+O\left(\psi(x) \right)$$
Lemma 1:  $\theta(x)\leq 3x$
The proof of this is postponed until the end.
Now, since $\theta(x)=\psi (x)+O(\sqrt{x})$, we have $\psi(x)=O(x)$.  Combining this with the fact that $\sum_{n\leq x} \log n= x\log x + O(x)$ we see that $$\sum_{d\leq x} \frac{\Lambda(d)}{d}=\log x+O(1).$$  Since the sum over all the prime powers of $\frac{\Lambda(d)}{d}$ is bounded by a constant, we conclude $$\sum_{p\leq x}\frac{\log p}{p}=\log x+O(1).$$
Hope that helps,
Proof of Lemma 1:
Consider the binomial coefficient $$\binom{2N}{N}.$$ Notice that every prime in the interval $(N,2N]$ appears in the numerator. Then $$\prod_{N<p\leq2N}p\leq\binom{2N}{N}$$ Since  $$\binom{2N}{N}\leq(1+1)^{2N}=4^{N},$$ we see that $$\prod_{N<p\leq2N}p\leq4^{N},$$ and hence $\theta(2N)-\theta(N)\leq N\log4.$ Consider $N$ of the form $N=2^{r}.$ Then we get the list of inequalities: $$\theta\left(2\right)-\theta\left(1\right)\leq\log4$$ 
$$\theta\left(4\right)-\theta\left(2\right)\leq2\log4$$
$$\theta\left(8\right)-\theta\left(4\right)\leq4\log4$$
$$\theta(2^{r})-\theta\left(2^{r-1}\right)\leq2^{r-1}\log4$$
$$ \theta\left(2^{r+1}\right)-\theta\left(2^{r}\right)\leq2^{r}\log4.$$  
Summing all of these yields $$\theta\left(2^{r+1}\right)-\theta\left(1\right)\leq\left(2^{r}+\cdots+1\right)\log4\leq2^{r+1}\log4$$ for each $r$. For every $x$ in the interval $(2^{r},2^{r+1}]$ we have $\theta(x)\leq\theta(2^{r+1})$ so that $$\theta(x)\leq2^{r+1}\log4\leq x\cdot2\log4<3x$$ since $x>2^{r}$. Thus the result is proven.
A: This is an application of the Shapiro -Tauberian theorem.  Please see Tom Apostol's "Introduction to Analytic Number theory'' text. 
Theorem: Let $\{a(n)\}$ be a non negative sequence such that 


*

*$\displaystyle\sum\limits_{n \leq x }a(n) \biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(x)$ for all $x \geq 1$.


Then


*

*For $x \geq 1$ we have $$\sum\limits_{ n \leq x} \frac{a(n)}{n} = \log{x} + \mathcal{O}(1)$$

*There is a constant $A >0$ and an $x_{0} > 0$ such that $$\sum\limits_{ n \leq x} a(n) \leq Bx$$ for all $x \geq 1$.

*There is a constant $A>0$ and an $x_{0}>0$ such that $$\sum\limits_{ n \leq x} a(n) \geq Ax$$ for all $x \geq x_{0}$.
Lemma 1. We have $$\sum\limits_{n \leq x} \Lambda(n) \biggl[\frac{x}{n}\biggr] = \log[x]!$$ where $\Lambda(n)$ denotes the Von-Mangoldt function which is defined as $$\Lambda(n) = \biggl\{ \begin{array}{cc} \log{p} & \text{if} \ n=p^{m} \ \text{for some prime} \ p \\\ 0 & \text{otherwise}\end{array}$$
Proof. \begin{align*} \sum\limits_{n \leq x}\Lambda(n) \biggl[\frac{x}{n}\biggr] =\sum\limits_{n \leq x}\sum\limits_{d \mid n} \Lambda(d)=\sum\limits_{n \leq x } \log{n} = \log[x]! \quad \biggl[ \because \sum\limits_{d \mid n} \Lambda(d) = \log{n} \ \biggr]
\end{align*}
Lemma 2. $\displaystyle \sum\limits_{n \leq x} \Lambda(n)\biggl[\frac{x}{n}\biggr] = x\log{x}  + \mathcal{O}(\log{x})$.
Proof. Taking $f(t) = \log{t}$ in the Euler's Summation formula, we have 
\begin{align*}
\sum\limits_{n \leq x} \log{n} &= \int\limits_{1}^{x} \log{t} \ dt + \int\limits_{1}^{x} \frac{t-[t]}{t}\ dt - ( x -[x])\cdot \log{x} \\\ &= x\log{x} - x + 1 + \int\limits_{1}^{x} \frac{t-[t]}{t} \ dt + \mathcal{O}(\log{x}) \\\ &= x \log{x} + \mathcal{O}(\log{x}) \qquad \Biggl[ \because \int\limits_{1}^{t} \frac{t-[t]}{t} \ dt = \mathcal{O}\biggl(\int\limits_{1}^{t} \frac{1}{t} \ dt\biggr)=\mathcal{O}(\log{x})\Biggr]
\end{align*}
Corollary. Take $a(n)= \Lambda(n)$. By Shapiro-Tauberian theorem, we then have $$\sum\limits_{n \leq x} \frac{\Lambda(n)}{n} = \log{x} + \mathcal{O}(1)$$
Lemma 3. For $x \geq 2$ we have $$\sum\limits_{p \leq x}\biggl[\frac{x}{p}\biggr]\log{p} = x\log{x} + \mathcal{O}(x)$$
Proof. Since $\Lambda(n)=0$ unless $n$ is a prime power, we have $$\sum\limits_{n \leq x} \biggl[\frac{x}{n}\biggr]\Lambda(n)= \mathop{\sum\limits_{p} \sum\limits_{m=1}^{\infty}}_{p^{m} \leq x}\biggl[\frac{x}{p^{m}}\biggr] \Lambda(p^{m})$$
For $p^{m} \leq x$ we have $p \leq x$. Also $\displaystyle \Bigl[\frac{x}{p^{m}}\Bigr]=0$ if $p >x$, so we can write the last sum as $$\sum\limits_{p \leq x}\ \sum\limits_{m=1}^{\infty}\biggl[\frac{x}{p^{m}}\biggr]\log{p}=\sum\limits_{p \leq x} \biggl[\frac{x}{p}\biggr]\log{p} + \sum\limits_{p \leq x} \ \sum\limits_{m=2}^{\infty} \biggl[\frac{x}{p^{m}}\biggr]\log{p}$$
Now we prove that the last sum above is $\mathcal{O}(x)$.  We have 
\begin{align*}
\sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \biggl[\frac{x}{p^{m}}\biggr] &\leq \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \frac{x}{p^{m}} = x \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \biggl(\frac{1}{p}\biggr)^{m} \\\ &= x \sum\limits_{p \leq x} \log{p} \cdot \frac{1}{p^{2}} \cdot \frac{1}{1-\frac{1}{p}} = x \sum\limits_{p \leq x} \frac{\log{p}}{p(p-1)}\\\ & \leq \sum\limits_{n=2}^{\infty}\frac{\log{n}}{n(n-1)} = \mathcal{O}(x)
\end{align*}
Suppose you set $$\Lambda_{1}(n) = \biggl\{ \begin{array}{cc} \log{p} & \text{if} \ n \ \text{is a prime} \\\ 0 & \text{otherwise}\end{array}$$ then you have from the above Lemma $$\sum\limits_{n \leq x} \Lambda_{1}(n) \biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(x)$$ Now applying the Shapiro - Tauberian theorem with $a(n)= \Lambda_{1}(n)$ gives $$\sum\limits_{p \leq x} \frac{\log{p}}{p} = \log{x} + \mathcal{O}(1)$$


*

*Everything Can be found in Apostol's book. I just thought TeXing it here would be nice. 

