Chapter 5

For each positive integer \(n,\) let \(p_{n}\) denote the \(n\) th prime. Show that \(p_{n}=\Theta(n \log n)\).

For each positive integer \(n,\) let \(\omega(n)\) denote the number of distinct primes dividing \(n .\) Show that \(\omega(n)=O(\log n / \log \log n)\).

For each positive integer \(k,\) let \(P_{k}\) denote the product of the first \(k\) primes. Show that \(\varphi\left(P_{k}\right)=\Theta\left(P_{k} / \log \log P_{k}\right)\) (here, \(\varphi\) is Euler's phi function).

The previous exercise showed that \(\varphi(n)\) could be as small as (about) \(n / \log \log n\) for infinitely many \(n\). Show that this is the "worst case," in the sense that \(\varphi(n)=\Omega(n / \log \log n)\).

Use Chebyshev's theorem and Abel's identity to prove a stronger version of Theorem 5.5: \(\vartheta(x)=\pi(x) \log x+O(x / \log x)\).

Use Chebyshev's theorem and Abel's identity to show that $$ \sum_{p \leq x} \frac{1}{\log p}=\frac{\pi(x)}{\log x}+O\left(x /(\log x)^{3}\right) $$

Strengthen Theorem 5.10: show that for some constant \(A,\) we have \(\sum_{p \leq x} 1 / p=\log \log x+A+o(1)\). You do not need to estimate \(A,\) but in fact \(A \approx 0.261497212847643 .\)

Use Abel's identity to derive Euler's summation formula: if \(f(t)\) has a continuous derivative \(f^{\prime}(t)\) on the interval \([a, b],\) where \(a\) and \(b\) are integers, then $$\sum_{i=a}^{b} f(i)-\int_{a}^{b} f(t) d t=f(a)+\int_{a}^{b}(t-\lfloor t\rfloor) f^{\prime}(t) d t$$.

Use Euler's summation formula (previous exercise) to show that $$\log (n !)=n \log n-n+\frac{1}{2} \log n+O(1)$$ and from this, conclude that \(n !=\Theta\left((n / e)^{n} \sqrt{n}\right) .\) This is a weak form of Stirling's approximation; a sharper form states that \(n ! \sim(n / e)^{n} \sqrt{2 \pi n}\).

Use Stirling's approximation (previous exercise) to show that $$ \left(\begin{array}{c} 2 m \\ m \end{array}\right)=\Theta\left(2^{2 m} / \sqrt{m}\right). $$

Design and analyze an algorithm that on input \(n\) outputs the table of values \(\tau(k)\) for \(k=1, \ldots, n,\) where \(\tau(k)\) is the number of positive divisors of \(k\). Your algorithm should run in time \(O(n \operatorname{len}(n))\).

Using the prime number theorem, show that \(\vartheta(x) \sim x\).

Using the prime number theorem, show that \(p_{n} \sim n \log n,\) where \(p_{n}\) denotes the \(n\) th prime.

Using the prime number theorem, show that Bertrand's postulate can be strengthened (asymptotically) as follows: for every \(\varepsilon>0,\) there exist positive constants \(c\) and \(x_{0},\) such that for all \(x \geq x_{0},\) we have $$\pi((1+\varepsilon) x)-\pi(x) \geq c \frac{x}{\log x}.$$