§ 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:
  • f(n)Hnlognf(n) \equiv H_n - \log n which starts at f(1)=1f(1) = 1 and strictly decreases.
  • g(n)Hnlog(n+1)g(n) \equiv H_n - \log(n+1) start lower at g(1)1log2g(1) 1 - \log 2 and strictly increases. [why? ]
  • Also, limnf(n)g(n)=0\lim_n f(n) - g(n) = 0. So these sandwhich something in between, which is the constant γ\gamma.