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), ................. and (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.
So far I know I have to count those pair (A,B) where A is divisible by B .Hence if I find out the number of divisors of all the numbers up to N,we will have the number of pair GCD(A,B)=B.
For example,for N=10,the number of divisor of 1 is 1, the number of divisor of 2 is 2,.............,the number of divisor of 10 is 4.So the total pair is 1+2+2+3+2+4+2+4+3+4=27.Since we want to remove those pair of B^2=A and the number of this kind of pair is 3.So our desired result will be 24.
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
Q1: Why we have to take summation of (floor(N/B)-B) where B is up to sqrt(N)?
Q2: why we have to subtract B from floor(N/B)?
Q3: why we have to multiply 2 with ((floor(10/1) - 1) + (floor(10/2) - 2) + (floor(10/3) - 3)) ?
Can anyone explain the reasoning behind the above method in details and clearly?
possible pairs.They are (1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5), ................. and (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.
So far I know I have to count those pair (A,B) where A is divisible by B .Hence if I find out the number of divisors of all the numbers up to N,we will have the number of pair GCD(A,B)=B.
For example,for N=10,the number of divisor of 1 is 1, the number of divisor of 2 is 2,.............,the number of divisor of 10 is 4.So the total pair is 1+2+2+3+2+4+2+4+3+4=27.Since we want to remove those pair of B^2=A and the number of this kind of pair is 3.So our desired result will be 24.
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
Q1: Why we have to take summation of (floor(N/B)-B) where B is up to sqrt(N)?
Q2: why we have to subtract B from floor(N/B)?
Q3: why we have to multiply 2 with ((floor(10/1) - 1) + (floor(10/2) - 2) + (floor(10/3) - 3)) ?
Can anyone explain the reasoning behind the above method in details and clearly?