Computing the number of ordered pairs of integers $(k_1, k_2)$ such that $k_1k_2 \leq N$ for a given value of $N$ I'm asking this question in context with a more larger computer science problem.
Let $k_1$ and $k_2$ be two natural problems such that their product $k_1k_2 \leq N$. What is the number of possible values of the ordered pair $(k_1,k_2)$ such that the product is smaller than $N$?
I am thinking that it has to do with the number of divisors of numbers smaller than $N$, but don't know how to approach it. Since $k_1k_2 \leq N$ implies $k_1 \leq N/k_2$, we could look for all natural values of $k_2$, and then find an inequality for $k_1$; add up the number of possible values of $k_1$ for each mentioned case. However, this is a computational solution, and I am looking for an analytic one.
 A: If for every natural integer $n$, $d(n)$ is the number of (positive) divisors of $n$, then the number of ordered pairs $(k_1,k_2)$ such that $k_1k_2\leq N$ is simply
$$\sum_{n=1}^N d(n)$$
as for every divisor $k$ of $n$, $n/k$ also is an integer, and every ordered pair has been counted once and only once. This method is called filtering.
A: The number can be calculated by $\displaystyle\sum_{n=1}^N d(n)$ where $d(n)$ is the number of positive divisors of $n$, but this can be more efficiently calculated as $\displaystyle\sum_{k=1}^N \left\lfloor \frac{N}{k}\right\rfloor$. This can be directly calculated from the problem. Just observe that for each possible value of $k_1$ there are $\left\lfloor \frac{N}{k_1}\right\rfloor$ possible values for $k_2$.
An even more efficient formula is $\displaystyle 2\sum_{k=1}^{\lfloor\sqrt{N}\rfloor} \left\lfloor \frac{N}{k}\right\rfloor - \lfloor\sqrt{N}\rfloor^2$
Approximating with high accuracy this sum is a well studied problem in Analytic Number Theory known as the divisor problem.
