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

  • $\begingroup$ 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$ $\endgroup$ – Namaste Apr 7 '14 at 12:22
  • $\begingroup$ @amWhy My edit is based on that observation. $\endgroup$ – drhab Apr 7 '14 at 12:23
  • $\begingroup$ Ah...missed the edit. Thanks, @drhab. I'll leave my question, just in case the OP wants to reply differently. $\endgroup$ – Namaste Apr 7 '14 at 12:24
  • $\begingroup$ I wouldn't call it a duplicate, but this recent question raises similar issues. $\endgroup$ – David Apr 7 '14 at 12:28
  • $\begingroup$ Is this a duplicate? Looking for opinion of others before voting. $\endgroup$ – Guy Apr 7 '14 at 13:02

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.