solving a number theoretical problem

Question

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Given an integer N. Now Find how many GCD(A,B)=B Where 1≤A≤B≤N For example,for N=3 the result will be 5.It can be found in the following way.

GCD(1,1)=1 OK

GCD(1,2)=1

GCD(1,3)=1

GCD(2,1)=1 OK

GCD(2,2)=2 OK

GCD(2,3)=2

GCD(3,1)=1 OK

GCD(3,2)=1

GCD(3,3)=3 OK

Here we get 5 combination where GCD(A,B)=B But how can I calculate it for 1≤N≤10^9 efficiently?

Answer 1

Hint: $\mathrm{gcd}(a,b) = b$ iff $b|a$. Since you're only looking for pairs in which $a \leq b$, this forces $a = b$.

Answer 2

You could try using Stein's method, which is especially efficient on binary computers:

$$\gcd(0,v) = v$$ $$\gcd(2u,2v) = 2 \gcd(u,v)$$ $$\gcd(2u+1,2v) = \gcd(2u+1,v)$$ $$\gcd(2u,2v+1) = \gcd(u,2v+1)$$ $$\gcd(2u+1,2v+1) = \gcd(u-v,2v+1)$$

That is:

$$\hbox{gcdcheck}(0,v) = \hbox{true}$$ $$\hbox{gcdcheck}(2u,2v) = \hbox{false}$$ $$\hbox{gcdcheck}(2u+1,2v) = \hbox{false}$$ $$\hbox{gcdcheck}(2u,2v+1) = \hbox{gcdcheck}(u,2v+1)$$ $$\hbox{gcdcheck}(2u+1,2v+1) = \hbox{gcdcheck}(u-v,2v+1)$$

Now implement this using dynamic programming. Use the fact that only the (odd,odd) cases need to be stored.

Answer 3

Looking at your worked out example, I believe that where you said 1≤A≤B≤N you meant 1≤B≤A≤N. And then your gcd equation only happens if B divides A.

If that is true, then your equation is equivalent to the following. How many pairs (B, A) are there with both less than or equal to N such that A = B * C for some C?

And now we can break into three cases. The cases are:

1. B < C
2. B = C
3. C < B

The number in case 2 is the floor of sqrt(N).

The number in cases 1 and 3 are the same.

The only hard part that is left is counting the number in case 1. And for that we can just run through the possible values of B up to sqrt(N), for each one adding floor(N/B) - B.

In the case of N = 3 the calculation then becomes floor(sqrt(3)) + 2 * ( floor(3/1) - 1) ) = 1 + 2 * (3 - 1) = 5.

This is not very informative, so let's do the case of N = 10. Then the calculation becomes

floor(sqrt(10)) + 2 * ((floor(10/1) - 1) + (floor(10/2) - 2) + (floor(10/3) - 3))
  = 3 + 2 * ((10 - 1) + (5 - 2) + (3 - 3))
  = 3 + 2 * (9 + 3 + 0)
  = 27

This equation requires O(sqrt(N)) terms. So for N around a billion you'll need to do tens of thousands of operations, which is not hard on current computers.