Given integers $N$ and $D$, find how many pairs of integers $(i, j)$ such that $1 \le i \le j \le N$ have the greatest common divisor exactly $D$.

I know it involves Mobius inversion somehow, but I can't seem to get the exact expression. The constraints on $N$ and $D$ are quite large (of the order of $10^8$), so it should be a direct formula.

  • 2
    $\begingroup$ Nice question but this is a question of ongoing contest. You could have asked it after the contest ends. You should not ask it while contest is still running. Link: codechef.com/LTIME26/problems/PUPPYGCD $\endgroup$ – Nimit Jul 26 '15 at 8:08

Since $D$ must divide both $i$ and $j$, you can divide everything through by $D$ immediately and reduce to: how many pairs $(k,\ell)$ of integers such that $1\le k\le \ell \le M$ have $\gcd(k,\ell)=1$, where $M=\lfloor N/D \rfloor$.

By the characteristic property of the Möbius function, the answer is $$ \sum_{1\le k\le\ell\le M} \sum_{d\mid\gcd(k,\ell)} \mu(d) = \sum_{1\le d\le M} \mu(d) \sum_{\substack{k\le\ell\le M \\ d\mid k,\, d\mid\ell}} 1 = \sum_{d\le M} \mu(d) \frac12 \bigg\lfloor \frac Md \bigg\rfloor \bigg( \bigg\lfloor \frac Md \bigg\rfloor + 1 \bigg). $$ This is approximately $$ \frac{M^2}2 \sum_{d=1}^\infty \frac{\mu(d)}{d^2} = \frac{3M^2}{\pi^2}. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.