# question on combinatorics and number theory

We have an equation as: $a\times b < n$ where $n$ is any positive integer. Now my question is how many pairs of positive integers $(a,b)$ can be found to satisfy the equation. For example, $a\times b < 3$ then the answer is $3$ as we have pairs $(1,1)$, $(1,2)$ and $(2,1)$.

• Given your solution to $n = 3$, it seems you require $a, b \in \mathbb N$, $a, b > 0$? Otherwise, there'd be infinitely many solutions $(a, b)$, for integers $a, b$ – Namaste Apr 7 '14 at 12:22
• @amWhy My edit is based on that observation. – drhab Apr 7 '14 at 12:23
• Ah...missed the edit. Thanks, @drhab. I'll leave my question, just in case the OP wants to reply differently. – Namaste Apr 7 '14 at 12:24
• I wouldn't call it a duplicate, but this recent question raises similar issues. – David Apr 7 '14 at 12:28
• Is this a duplicate? Looking for opinion of others before voting. – Guy Apr 7 '14 at 13:02

## 1 Answer

Well, if you define $d(k)$ as the number of divisors of $n$, the number of pair $(a,b)$ such that $ab=k$ is exactly $d(k)$, since for each divisor $a$ you have the pair $(a, k/a)$.

But what you are questioning about is the sum $$\sum_{k=1}^{n-1}d(k)$$.

This is not a trivial matter, but there is a result obtained by Dirichlet in 1849:

$$\sum_{k\leq x} d(k)=x\log x+(2C-1)x+O(\sqrt x)$$

You can find a proof in Introduction to Analytic Number Theory by Tom M. Apostol. I'd write it here, but it is pretty long.