Number of ordered pairs $(a,b)$ such that $ab \le 3600$

Question

Find number of ordered pairs $(a,b)$ such that $ab\le 3600$ and $a,b \in N$

My attempt : Well, all $a,b \leqslant 60$ are solutions. These 3600 solutions. After that I have no idea how to count the number of remaining solutions...

I have a feeling that my approach is $very$ bad. But I had to give as it would be marked as off-topic.

@NicholasR.Peterson: that is one of the remaining ones. We get it from the doubling of the case $a=1,b=3600$ — Ross Millikan, Mar 26 '14 at 19:08
@RossMillikan I was responding to his claim that $a,b\leq 60$. — Nick Peterson, Mar 26 '14 at 20:06
@NicholasR.Peterson: I think the word "the" is extraneous. He seemed to be saying that those are solutions, but knew there were more and wanted help counting them. — Ross Millikan, Mar 26 '14 at 20:19

score 3 · Accepted Answer · answered Mar 26 '14 at 13:22

3

Hint: First, you can count only those pairs where $a \lt b$, double them, and add one for $(60,60)$ We know $a \lt 60$. How many are there for $a=1$? How many are there for $a=2$? Can you write an expression for general $a$? Then add them up for $a$ from $1$ to $59$.

answered Mar 26 '14 at 13:22

Ross Millikan

374,822

2

$2 \sum\lfloor{\frac{3600}{a}}\rfloor+1$ – evil999man Mar 26 '14 at 13:25
feels right? – evil999man Mar 26 '14 at 13:27
1

Yes, that is correct. Good work. – Ross Millikan Mar 26 '14 at 13:27
Thanks... Now let me guess... there is a nice way of summing this? – evil999man Mar 26 '14 at 13:30
Well...not one wolfram alpha knows of. – evil999man Mar 26 '14 at 13:40
No, I don't know one. You can get close with the harmonic numbers, but that doesn't include the floor function. But you now have a $O(\sqrt n)$ problem, as you only have $60$ things to add up instead of $3600$ – Ross Millikan Mar 26 '14 at 13:45
It is similar to the Gauss circle problem, which asks how many lattice points are in a circle. You are asking how many are under a hyperbola. I don't think either has a nice form. – Ross Millikan Mar 26 '14 at 13:49
Thanks. – evil999man Mar 26 '14 at 13:52
@Awesome: for a,b > 0, you mean $2 \sum _a^z \left\lfloor \frac{z^2}{a}\right\rfloor -z^2$ with z=60? so 30060 ? – Wouter M. Mar 26 '14 at 18:57
@Awesome: or $\sum _a^{z^2} \sigma _0(a)$ see http://oeis.org/A175346 – Wouter M. Mar 26 '14 at 19:04
@WouterM. I have no idea what that means – evil999man Mar 27 '14 at 03:12
@Awesome: sum of number of divisors of a for a = 1 .. 60^2 equals -(60^2)+2sum of floor(60^2/a) for a = 1 .. 60; so the number of ordered pairs (a,b) with (a,b)>0 and ab<=60^2 equals 30060; is this something that helps? – Wouter M. Mar 27 '14 at 11:19
@WouterM. Can you please explain how did you get 30060? – evil999man Mar 27 '14 at 11:37
Won't the answer be $\sum\frac{3600}{a}$ from a=1 to 3600? – evil999man Mar 27 '14 at 11:41
take z=4 as example, so we're looking for pairs (a,b) such that ab<=16, then we get 23 pairs: 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 31, 32, 33, 41, 42, 51, 61, 71, 81, 91 ; Rows 1 to 9 have length 9, 4, 3, 2, 1, 1, 1, 1, 1 and they form a symmetric tableau; we need only count the first 3 rows and take twice that but correcting for double-counting the square from 11 to 33; hence -(3^2)+2*sum of floor(3^2/a) for a = 1 .. 3; I leave it to you to prove that this also equals sum of number of divisors of a for a = 1 .. z^2 – Wouter M. Mar 27 '14 at 15:23
... got hit by the 5 min edit rule: take z=3 as example, so we're looking for pairs (a,b) such that a*b<=9, then we get 23 pairs etc ... – Wouter M. Mar 27 '14 at 15:44
@WouterM., could you please write that out as an answer? I'd like to have a better understanding of what you are doing. I'm asking a similar question. – abalter Jun 13 '14 at 21:31

Wouter M. · Answer 2 · 2014-06-14T14:07:16.510

You ask for the count of ordered pairs of integers (a,b) such that a*b <= n.
Set up a table in which the first row fixes a to 1: this allows b to run from 1 to n.
In the k'th row, we fix a to value k, so b runs from 1 to floor(n/k).
The table is obviously symmetrical across the diagonal (1,1), .. (q,q) with q=floor(sqrt(n))). This allows us to simplify the counting to a running from 1 to q, take twice that, and subtract the double counting of the square q^2.
Using Mathematica:
Table[q = Floor[Sqrt[n]]; 2*Sum[Floor[n/k], {k, q}] - q^2, {n, 16}]
or {1,3,5,8,10,14,16,20,23,27,29,35,37,41,45,50}
But, looking it up produces http://oeis.org/A006218 :
Table[ Sum[DivisorSigma[0,k],{k,n} ],{n,16}] normally written as $\sum _k^n \sigma _0(k)$ alias the sum of (the count of divisors of k) for k running from 1 to n.
The challenge is to prove both counts to be equal.
Looking down the columns of the above table, we see that the entry in row k is 1 larger than that in row k-1 if floor(n/k) > floor(n/(k-1)), and that again happens only if k is a divisor of n. So, within row k, the entries in column j are 1 larger than in row k-1 exactly if j divides n. Not very challenging after all.

Number of ordered pairs $(a,b)$ such that $ab \le 3600$

2 Answers2

Linked

Related