# How many pairs of integers $(A, B)$ are there in the range $[1,\ldots, N]$, such that $\gcd(A,B) = B$?

I am given a positive integer $N$ ($N\leq 10^9$).

How many pairs of integers $(A, B)$ exist in the range $[1,\ldots, N]$ such that $\gcd(A,B) = B$?

-
It seems very similar a question for a current programming contest. –  ILikeMath Sep 8 '13 at 19:28

We have $\gcd(A, B)=B$ if and only if $B$ divides $A$. So the desired number of pairs would be $$2\left(\sum_{i=1}^{N} \lfloor N/i \rfloor\right)-N$$ We need to subtract $N$, otherwise the pairs $(i, i)$ would be counted twice. Here $\lfloor N/i \rfloor$ accounts for the number of multiples of $i$ up to $N$.

Added. The above formula counts $(A, B)$ and $(B, A)$ as solutions whenever $B$ divides $A$. But the number of ordered pairs $(A, B)$ with $B$ dividing $A$ would simply be: $$\sum_{i=1}^{N} \lfloor N/i \rfloor$$ Here the index $i$ plays the role of $B$.

-
Any possible closed formula? Computing this formula with a c++ code will take too much time ( around 10 seconds ). –  Ahmedou Mousa Sep 8 '13 at 19:27
@AhmedouMousa: I don't know of a closed formula, unfortunately. –  Prism Sep 8 '13 at 19:35
good answer i just wrote a big answer assuming $N = 10^9$ and not $N \leq 10^9$ :( . (+1) –  what'sup Sep 8 '13 at 19:47
For $N=3$ the formula gives $2(\lfloor 3/1 \rfloor + \lfloor 3/2 \rfloor+ \lfloor 3/3 \rfloor ) - 3 = 2(3 + 1 + 1) - 3 = 7$. But I can only find 5 pairs where $gcd(a,b) = b$: $(1,1), (2,1), (3,1), (2,2), (3,3)$ What am I missing? –  Andomar Sep 8 '13 at 19:53
there are & ordered pairs in your answer @Andomar –  Ahmedou Mousa Sep 8 '13 at 19:59

There are good estimates available.

d(n)=nlogn+(2γ−1)n for very large n

γ=en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant

-
what is the value for gamma ? –  user94657 Sep 13 '13 at 10:09