How many pairs $(A,B)$ of integers up to $n$ are there such that $\gcd(A,B)=B$, not counting those pairs where $B^2=A$?
If we consider $n = 5$ we have $25$ possible pairs. They are $$(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),\dotsc,(5,5)$$
Of them, $8$ pairs satisfy the above condition. My main objective is to find the number of such pairs if $n$ is given, with a efficient method. One of my friends showed me a method but he didn't state the reasoning behind it.
Here, I'm presenting his method for $n=10$. $$ \begin{align} & 2 \cdot \left(\left(\left\lfloor\frac{10}{1}\right\rfloor - 1\right) + \left(\left\lfloor \frac{10}{2} \right\rfloor - 2\right) + \left(\left\lfloor \frac{10}{3} \right\rfloor - 3\right)\right) \\ =& 2 \cdot ((10 - 1) + (5 - 2) + (3 - 3)) \\ =& 2 \cdot (9 + 3 + 0) \\ =& 24 \end{align} $$ Can anyone explain the reasoning behind the above method in details and clearly?
Observe that $\gcd(a,b) = b$ if and only if $b$ divides $a$, so you want to add the number of multiples of $b$ less or equal than $n$ for every $b \leq n$. To remove the pairs $(b^2,b)$ you just need to subtract the number of perfect squares less or equal than $n$. Putting it together, the formula you're looking for is: $$ \sum_{b = 1}^n \left\lfloor \frac{n}{b} \right\rfloor - \left\lfloor \sqrt{n} \right\rfloor $$ Your friend is probably exploiting some symmetry of this formula.