Given $n\geq1$, how can I count the number of pairs $(a,b)$, $0\leq a,b \leq n$ such that $gcd(a,b)=1$?
I think the answer is $2\sum_{i}^{n}\phi(i)$. Am I right?
Given $n\geq1$, how can I count the number of pairs $(a,b)$, $0\leq a,b \leq n$ such that $gcd(a,b)=1$?
I think the answer is $2\sum_{i}^{n}\phi(i)$. Am I right?
Easy. From the points in $G=\{(x,y)|1\leq x,y\leq n\}\cap\mathbb{Z}^2$, take away all points $Q\in G$ for which another, distinct (smaller) point $P\in G$ lies on the line segment $\overline{OP}$ between $P$ and the origin $O(0,0)$. Call the set of remaining poins $H$. There is thus one point $(1,1)\in H$ on the line $y=x$, the same number of points above and below $y=x$, and one point on each axis (thank you @pedja!). This will give us $3+2f(n)$ points for some function $f$ of $n$: $ f(n)=\#\left\{\frac{a}{b} : 0 since there are $\phi(b)$ choices for $1\leq a. Hence $ \#H = 3+2\sum_{k=2}^n\phi(k) = 1+2\sum_{k=1}^n\phi(k). $ Also, since $\sum_{0
The answer is in fact quite interesting. Let's define the function $p(n)$ to be the number of pairs you ask for. It is not hard to see that
$p(n) = n^2 - \sum_{k=2}^{n} p(\lfloor n/k \rfloor)$
Quick explanation. You count all pairs as $n^2$but you over counted. You take out all pairs $(k*a', k*b')$ for all $k \geq 2$ and $\gcd(a', b') = 1$, which is precisely the sum over $p(\lfloor n/k \rfloor)$.
We notice that $p(n) = p(\lfloor n/1\rfloor)$, therefore we can rewrite the equation as
$n^2 = \sum_{k=1}^{n} p(\lfloor n/k \rfloor)$ (notice how the sum starts from 1 now).
We then apply the Möbius inversion formula. We get
$p(n) = \sum_{k=1}^{n}\mu(k)\lfloor n/k \rfloor^2$
where $\mu(n)$ is the Möbius function.
On a more computational note, $\mu(n)$ can be computed in $O(\sqrt n)$. Also, the sequence $(\mu(1), ..., \mu(n))$ can be computed in O(n). Sample implementations are here.
NOTES:
you are looking for Euler's totient function:
Definition :
$\phi(n) ~$ is the number of integers $k$ in the range $1 ≤ k ≤ n$ for which $\gcd(n, k) = 1$
Let's denote number of pairs $(a,b)$ as $N$ then :
$N= 2\cdot\displaystyle \sum_{i=1}^{n} \phi(i)+1 $
This is because you have to add pairs $(0,1) ~~\text {and}~~ (1,0)~~\text {and}~~ $pair $(1,1)$ can be included only once time .
Perhaps it could be mentioned that if we consider the probability $P_{n}$ that two randomly chosen integers in $\{1, 2, \dots, n \}$ are coprime $ P_{n} = \frac{\lvert \{(a, b) : 1 \le a, b \le n, \gcd(a,b) =1 \}\rvert}{n^{2}}, $ then $ \lim_{n \to \infty} P_{n} = \frac{6}{\pi^{2}}. $