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)$.
Asked
Active
Viewed 65 times
0
-
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$ – amWhy Apr 07 '14 at 12:22
-
@amWhy My edit is based on that observation. – drhab Apr 07 '14 at 12:23
-
Ah...missed the edit. Thanks, @drhab. I'll leave my question, just in case the OP wants to reply differently. – amWhy Apr 07 '14 at 12:24
-
I wouldn't call it a duplicate, but this recent question raises similar issues. – David Apr 07 '14 at 12:28
-
Is this a duplicate? Looking for opinion of others before voting. – Guy Apr 07 '14 at 13:02
-
Computing the first several terms of a sequence and checking with the OEIS is often a good idea. In this case you get https://oeis.org/A006218 – Barry Cipra Apr 07 '14 at 13:11
-
@Sabyasachi I think you are right. – drhab Apr 07 '14 at 14:44
1 Answers
0
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.
ajotatxe
- 65,084