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:

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$.