Im trying to solve the exercise 13.2 in Apostol's analytic number theory book: Let $A(x)=\sum_{n\leq x}a(n)$, where $a(n)$ is zero unless $n=p^k$ for some prime $p$, in that case $a(n)=1/k$. Prove that $A(x)=\pi(x)+O(\sqrt{x}\log \log x)$.

I've tried things like this: By the definition of the function $a$, we have that \begin{equation*}A(x)=\underset{p\leq x}{\sum}\sum_{\substack{k\in \mathbb{Z}^+\\ p^k\leq x}}a(p^k)+1=\underset{p\leq x}{\sum}\sum_{\substack{k\in \mathbb{Z}^+\\ p^k\leq x}}\frac{1}{k}.\end{equation*} The last formula holds for $x\geq 1$. Look that, for all $k\in \mathbb{Z}^+$, we have the following $$p^k\leq x \iff k\log p=\log (p^k)\leq \log x \iff k \leq \log_p(x).$$ Here $\log_p x:=\frac{\log x}{\log p}$. By all this and theorem 3.2 from Apostol, we get

\begin{eqnarray*} A(x) & = & \underset{p\leq x}{\sum}\sum_{\substack{k\in \mathbb{Z}^+\\ p^k\leq x}}\frac{1}{k}= \underset{p\leq x}{\sum}\sum_{\substack{k\in \mathbb{Z}^+ \\ k\leq \log _p x}}\frac{1}{k}= \underset{p\leq x}{\sum}[\log \log_p x + C + O(\frac{\log p}{\log x})]\\ & = & \underset{p\leq x}{\sum}O(\log \log x)+\underset{p\leq x}{\sum}C+\underset{p\leq x}{\sum}O(\log^{-1}x)\\ & = & O(\log \log x)\underset{p\leq x}{\sum}1+C\underset{p\leq x}{\sum}1+O(\log^{-1}x)\underset{p\leq x}{\sum}1\\ & = & O(\log \log x)\pi(x)+(C-1+1)\pi(x)+O(\log^{-1}x)\pi(x)\\ & = & O(\log \log x)O(\frac{x}{\log x})+(C-1)O(\frac{x}{\log x})+\pi(x)+O(\log^{-1}x)O(\frac{x}{\log x}). \end{eqnarray*}

Could someone please help me finishing this exercise?

Due to Greg Martin's answer (again) i made this solution:

First, look that if $k$ is a positive integer suchthat $p^k \leq x$ for some prime $p$, then $2^k \leq p^k \leq x$, so $k\log 2=\log 2^k\leq \log x$ and $k\leq \log_2 x$.


\begin{eqnarray*} A(x) & = & \sum_{k\in \mathbb{Z}^{+}} \sum_{\substack{p \text{ prime}\\ p^k \leq x}} \frac{1}{k}=\sum_{k=1}^{[\log_2 x]}\frac{1}{k}\sum_{\substack{p \text{ prime}\\ p \leq x^{1/k}}}1\\ & = & \sum_{k=1}^{[\log_2 x]}\frac{\pi(x^{1/k})}{k}\\ & = & \pi(x)+\sum_{k=2}^{[\log_2 x]}\frac{\pi(x^{1/k})}{k}\\ & = & \pi(x) +\sum_{k=2}^{[\log_2 x]} \frac{\overbrace{x^{1/k}/\log x^{1/k}+o(x^{1/k}/\log x^{1/k})}^{\text{by the prime number theorem}}}{k}\\ & = & \pi(x)+\sum_{k=2}^{[\log_2 x]}\frac{x^{1/k}}{k \log x^{1/k}}+ \sum_{k=2}^{[\log_2 x]}\frac{\overbrace{O(x^{1/k}/\log x^{1/k})}^{\text{every }o\text{ is }O}}{k}\\ & = & \pi(x)+\frac{1}{\log x}\sum_{k=2}^{[\log_2 x]} x^{1/k}+O(\sum_{k=2}^{[\log_2 x]}\frac{x^{1/k}/\log x^{1/k}}{k}) \\ &=& \pi(x)+\frac{1}{\log x}O(\sqrt{x}\log x)+O(\frac{1}{\log x}\sum_{k=2}^{[\log_2 x]} x^{1/k})\\ &=&\pi(x) +O(\sqrt{x})+O(\frac{1}{\log x}O(\sqrt{x}\log x))\\ &=& \pi(x) +O(\sqrt{x})=\pi(x) +O(\sqrt{x}\log \log x). \end{eqnarray*}

In the seventh equality we used the following $$\sum_{k=2}^{[\log_2 x]}x^{1/k}\leq \sum_{k=2}^{[\log_2 x]}\sqrt{x}\leq \sqrt{x}\log_2 x=\frac{\sqrt{x}\log x}{\log 2} \text{ for all }x\geq 1.$$

  • 1
    $\begingroup$ That is a very well formatted question, which is rare these days. Congratulations. $\endgroup$ – Klangen Jul 25 '17 at 21:22

Unfortunately, once you have error terms like $O(x/\log x)$, you're not going to be able to recover and obtain the desired $O(\sqrt x \log\log x)$.

I suggest that you first establish the identity $$ A(x) = \pi(x) + \tfrac12\pi(\sqrt x) + \tfrac13\pi(\sqrt[3]x) + \cdots. $$ (Hint: instead of sorting first by $p$, sort first by $k$.) From there you should be able to obtain the desired result (indeed, if you're careful, you can get $O(\sqrt x/\log x)$ even).

PS: I think $a(1)=0$.

  • $\begingroup$ Thanks Greg. I wrote a solution due to your suggestion. $\endgroup$ – Evangelion045 Jun 12 '14 at 16:45

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.