Solving a number theoretical problem (1 Viewer)

[mamun11]

How many pairs(A,B) are there up to n such that GCD(A,B)=B without those pairs(A,B), where B^2=A.
If we consider 5 as n 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),...,(5,5).

Of them, 8 pairs satisfy the above condition.My main objective is to find out 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.

2 * ((floor(10/1) - 1) + (floor(10/2) - 2) + (floor(10/3) - 3))

= 2 * ((10 - 1) + (5 - 2) + (3 - 3))

= 2 * (9 + 3 + 0)

= 24

Can anyone explain the reasoning behind the above method in details and clearly?

 

[seanieg89]

Okay, well first note that gcd(A,B)=B is equivalent to just saying that B divides A. (Let me know if you don't see why this is the case).

So let's count the number of pairs of positive integers not exceeding N such that B|A.

This is the same as letting B vary between 1 and N, and counting the number of multiples of B that do not exceed N.
'
This is just

Given the non-square condition, we need to subtract 1 when B does not exceed

Hence, the number you are looking for is

 

[seanieg89]

As an extension, you might find it interesting to try and prove that



where is the quantity in the question and log is the natural log.