# A bizarre expression for cardinality involving summation of roots and floor function

Show that number of triples $$(a,b,c)$$ with $$a,b,c\in [1,n]$$ such that $$ab=c$$ is given by

$$\bigl|\bigl\{(a,b,c)\in [1,n]^3:ab=c\bigr\}\bigr|=2\sum_{i=1}^{\left\lfloor\sqrt{n}\right\rfloor}\Big(\left\lfloor\frac ni\right\rfloor-i\Big)+\left\lfloor\sqrt{n}\right\rfloor$$

Someone told me that this can be solved using hyperbolas. I could not really understand how that would help. Please help!

It could have been easier if the interval were not a requirement, but that is the part that is confusing me the most.

• This is not bizarre, it's bog-standard introductory Number Theory. – Gerry Myerson Apr 26 at 5:08
• @GerryMyerson In my opinion, comments that pass a judgement, especially if that judgement is implying something that is hard for one person is rudimentary for another, fall under the not needed category unless they’re substantiated in some way. – gen-z ready to perish Apr 26 at 8:00
• @Chase, OP didn't write that it was hard, but that it was "bizarre". I didn't reply that it was rudimentary, but that it was standard. It is standard, it's exactly the kind of equation I'd expect to show up in a first course in Number Theory. It's no criticism of someone who hasn't seen it before to write that it's standard – it just tells them that it's not some outlandish thing that only their teacher has ever thought of, it's something one who has been there would expect to see. – Gerry Myerson Apr 26 at 8:49
• @Chase: after a Google search, it may be worthy to note that “bog-standard” just means that it’s plain, ordinary, or unexceptional. In this sense, I’m in agreement with Gerry Myerson; it might be comparable to the Fundamental Theorem of Calculus in a beginning calculus class - some students might find it difficult but it is definitely a standard resultnone expects to see in such a course. – Clayton Apr 26 at 12:46
• @Clayton, I should have remembered not everyone speaks Australian. – Gerry Myerson Apr 27 at 7:33

The idea is to count the number of triplets with $$a \lt b$$ in the sum and double it to account for reversing $$a$$ and $$b$$, then add in the triplets of the form $$(a,a,a^2)$$ with the last term. If a triplet has $$a \lt b$$, it also has $$a \lt \sqrt n$$ because otherwise $$ab \gt n$$. The sum therefore runs from $$1$$ to $$\lfloor \sqrt n \rfloor$$ because that is the range of values of $$a$$. $$\lfloor \frac ni \rfloor$$ is the number of multiples of $$i$$ that are less than or equal to $$n$$. We subtract $$i$$ for the cases where $$b \le a$$ and add the $$(a,a,a^2)$$ cases in with the $$\lfloor \sqrt n \rfloor$$.
Let us take an example of $$n=15$$, where $$\lfloor \sqrt n \rfloor=3$$. When $$i=1$$ there are $$\frac {15}1=15$$ multiples of $$1$$ less than or equal to $$15$$. One of those has $$b \le a$$, each of the others contributes two triplets and the term in the sum is $$14$$, which will get doubled at the end. When $$i=2$$ there are $$7$$ multiples of $$2$$ less than or equal to $$15$$, two of which have $$b \le a$$, so the entry in the sum is $$5$$. Finally there are four multiples of $$3$$ only one of which has $$b \gt a$$. The final calculation is $$2(14+5+2)+3=45$$ triplets.