§ The number of pairs (a,b) such that ab≤x is O(xlogx)

Fix a given a. ab ≤ x implies that b ≤ x/a, or there are only x/a possible values for b. If we now consider all possible values for a from 1 upto x, we get:

$$\begin{aligned} |{ (a, b) : ab <= x }| = \sum_{a=1}^x |{ b: b <= x/a }| \leq \sum_{a=1}^x |x/a| \leq x \sum_{a=1}^x (1/a) \leq x \log x \end{aligned}$$

To show that the harmonic numbers are upper bounded by $\log$, can integrate: $\sum_{i=1}^n 1/i \leq \int_0^n 1/i = \log n$

§ Relationship to Euler Mascheroni constant

This is the limit $\gamma \equiv \lim_{n \to \infty} H_n - \log n$. That this is a constant tells us that these functions grow at the same rate. To see that this si indeed a constant, consider the two functions:

• $f(n) \equiv H_n - \log n$ which starts at $f(1) = 1$ and strictly decreases.
• $g(n) \equiv H_n - \log(n+1)$ start lower at $g(1) 1 - \log 2$ and strictly increases. [why? ]
• Also, $\lim_n f(n) - g(n) = 0$. So these sandwhich something in between, which is the constant $\gamma$.