3
$\begingroup$

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?

  • 0
    $−1+2\cdot\sum\limits^n_{k=1}\phi(k)$ . what does $\phi(k)$ stands for ?2014-05-27

5 Answers 5

3

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 and $\phi(k) for $k>1$, we can (very roughly) say that $1+2n<\#H<1+n^2$ for $n>2$.

  • 0
    You should include pairs $(1,0)$ , and $(0,1)$...2012-02-12
1

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:

  • This was all explained to me in this thread a few years ago.
  • As noted in other (deleted) answers $-1 + 2*\sum_{k=1}^{n} \phi(k)$ would probably work too. You count all pairs $(a, b)$ where $a < b$ by summing over all b $\phi(b)$, then multiplying by 2 and noticing that $(1, 1)$ was counted twice. I can't see however how this would lead to an efficient algorithm.. On second thought, this can be done using a modification of the Sieve of Eratosthenes. See this.
  • The approach above extends to any k-tuple. You replace the power of 2 by k.
0

you are looking for Euler's totient function:

http://en.wikipedia.org/wiki/Euler%27s_totient_function

  • 0
    the original question was is there a way ... only a$f$ter being pointed to the totient function was the question amended, so down voting seems a little excessive ...2012-02-12
0

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 .

0

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}}. $

See this Wikipedia article.