4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is not bizarre, it's bog-standard introductory Number Theory. $\endgroup$ – Gerry Myerson Apr 26 at 5:08
  • $\begingroup$ @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. $\endgroup$ – gen-z ready to perish Apr 26 at 8:00
  • 1
    $\begingroup$ @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. $\endgroup$ – Gerry Myerson Apr 26 at 8:49
  • 1
    $\begingroup$ @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. $\endgroup$ – Clayton Apr 26 at 12:46
  • $\begingroup$ @Clayton, I should have remembered not everyone speaks Australian. $\endgroup$ – Gerry Myerson Apr 27 at 7:33
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 thank you! . $\endgroup$ – user665856 Apr 26 at 5:03

Your Answer

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