§ 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:
(a,b):ab<=x=a=1xb:b<=x/aa=1xx/axa=1x(1/a)xlogx \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\log, can integrate: i=1n1/i0n1/i=logn\sum_{i=1}^n 1/i \leq \int_0^n 1/i = \log n

§ Relationship to Euler Mascheroni constant


This is the limit γlimnHnlogn\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: