The sum of the reciprocals of the natural numbers diverges, but slowly, like the logarithm of the number of terms. The sum of the reciprocals of the prime numbers also diverges, but even more slowly, like the logarithm of the logarithm of the number of terms, as the primes are sparse in the naturals!

Here I attempt elementary proofs that

H_n = \sum_{m\le n} \frac{1}{m} = \mathcal{\Theta}(\log n),

where m,n \in \mathbb{N}_1 = \mathbb{Z}^+, and

S_n = \sum_{p\le n} \frac{1}{p} = \mathcal{\Theta}(\log \log n),

where p \in \mathbb{P} is a prime number, as in Fig. 1. In both cases, I will try to bound the sums below and above to show they are of the same order, a g(x) \le f(x) \le b g(x) so f(x) = \Theta(g(x)). The results are not new, but the presentation is.

Figure 1: Inverse numbers partial sums (red) increase like a log function, while inverse primes partial sums (blue) increase as the log of a log.

Sum of Reciprocals of Naturals

Lower Bound

The harmonic inverse numbers sum overestimates the corresponding integral as

H_n = \sum_{m=1}^n\frac{1}{m} >\int_1^{n+1}\hspace{-1.3em}\text{d}x\frac{1}{x} = \log(n+1),

where the sum is the area bounded by blue rectangles to the hyperbola 1/x, as in Fig. 2.

Figure 2: Tall blue rectangle sums overestimate the red integral area under the hyperbola, while short yellow rectangle sums underestimate it, for n=3.

Upper Bound

Similarly, the shifted sum underestimates the corresponding integral as

-1+H_n = -1 + \sum_{m=1}^n\frac{1}{m}= \sum_{m=2}^n\frac{1} {m}≤\int^n_{1}\hspace{-0.6em}\text{d}x\frac{1}{x} = \log n.

where the sum is the area bounded by short yellow rectangles to 1/x, and so

H_n ≤ \log n+1.

Tight Bound

Combine the lower and upper bounds to find

\log(n+1)<H_n≤\log n + 1,

and so

H_n = \sum_{m\le n} \frac{1}{m} = \mathcal{\Theta}(\log n).

Sum of Reciprocals of Primes

Lower Bound

The inverse numbers sum is dominated by

H_n = \sum_{m\le n} \frac{1}{m} < \sum_{n\ge p|m} \frac{1}{m} = \prod_{p\le n}\left(\sum_{k=0}^\infty \frac{1}{p^k}\right),

where the second sum is over all natural numbers m = p_1^{c_1} p_2^{c_2} \cdots p_r^{c_r} divisible by primes p \le n , which includes arbitrarily large m generated by the finite product of the infinite sum. The latter is a geometric series with start 1 and ratio 1/p, so

H_n < \prod_{p\le n} \left( 1-\frac{1}{p} \right)^{-1} < \prod_{p\le n} e^{2/p} = \exp\left({2\sum_{p\le n} 1/p}\right),

as e^{2/p} >1+2/p > (1-1/p)^{-1} for p\ge 2, and the product of exponentials is the exponential of the sum. Take logs of both sides to find

\log H_n < 2 \sum_{p\le n} \frac{1}{p} = 2 S_n

and since \log n < \log(n+1) < H_n from earlier,

S_n > \frac{1}{2} \log H_n > \frac{1}{2}\log\log n.

Upper Bound

Raise the inverse primes sum to the kth power and write it as a multidimensional sum over the inverse prime factors product

S_n^k = \left(\sum_{p\le n} \frac{1}{p}\right)^k = \hspace{-0.7em} \sum_{p_1,p_2,\cdots,p_k < n} \frac{1}{p_1 p_2\cdots p_k } < \sum_{m\le n^k} \frac{k!}{m},

as any reciprocal 1/m appears at most k! times with one prime from each of the k factors in any order in the product p_1p_2 \cdots p_k \le n^k. Since H_x \le \log x + 1 from earlier, write

S_n^k < k! H_{n^k} \le k! (\log n^k + 1) \le k!\, k\, 2\log n,

as 1 \le \log x for x \ge e > 2. Take the kth root of both sides to find

S_n < (k!\, k\, 2\log n)^{1/k} < k\, e\, 2(\log n)^{1/k},

as

\begin{aligned}(k!)^{1/k} &\le (k^k)^{1/k} = k, \\ k^{1/k} &= \left(e^{\log k}\right)^{1/k} = e^{(\log k) / k} < e^1 = e,\\ 2^{1/k} &\le 2,\end{aligned}

for k \ge 1. Now take k = \lfloor 1 + \log\log n \rfloor to get

\begin{aligned}S_n &< (1 + \log\log n) e 2 (\log n)^{1/(1+\log\log n)}\\ &= (1 + \log\log n) e 2 e^{\log\log n/(1+\log\log n)}\\ & \le (1 + \log\log n) e 2 e.\end{aligned}

Finally, for n \ge 3,

\begin{aligned}S_n &< 2e^2 \left(\frac{1}{\log\log n} + 1\right) \log\log n \\& \le 2e^2 \left(\frac{1}{\log\log 3} + 1\right) \log\log n \\& = C \log\log n,\end{aligned}

where the constant C = 2e^2(1/\log\log 3 + 1) \approx 172.

Tight Bound

Combine the lower and upper bounds to find

\frac{1}{2}\log\log n < S_n \lesssim 172 \log \log n,

and so

S_n = \sum_{p\le n} \frac{1}{p} = \mathcal{\Theta}(\log \log n).