# How many numbers with no common divisor are there?

There is quite general question.

Let $$A=\{1,2,3,...,n\}$$ be a set.

Calculate the following: $$W_{k}=\sum_{\substack{a_{1},...,a_{k}\in A\\ a_{i}\neq a_{j} \text{ if }i\neq j\\ \gcd(a_{1},...a_{k})=1}}\hspace{-1.5em}1$$

For example $$W_{2}=\sum_{2\le a \le N}\phi(a)$$

Where $$\phi$$ is Euler totient function.

But I have no idea how to carry it on.

I wonder whether inclusion-exclusion principle should be used.

I hope for help.

Regards.

• What kind of answer are you looking for? Even the $\sum \phi(n)$ doesn't have a closed form so far as I can tell. – saulspatz May 26 at 12:23
• @saul, but it does have good asymptotics. – Gerry Myerson May 26 at 12:58

We have $$W_k=W_k(n):=\#A(n,k,1)$$, where $$A(n,k,d)=\left\{(a_1,\ldots,a_k)\in\{1,\ldots,n\}^k\ \middle|\ \begin{gathered}i\neq j\implies a_i\neq a_j\\ \gcd(a_1,\ldots,a_k)=d\end{gathered}\right\}.$$ Now clearly $$\#A(n,k,d)=W_k(\lfloor n/d\rfloor)$$, and $$\bigcup_{d=1}^{n}A(n,k,d)$$ is the set of all $$k$$-tuples of distinct numbers from $$\{1,\ldots,n\}$$. This set has $$(n)_k=n(n-1)\cdots(n-k+1)$$ elements, which gives $$\sum_{d=1}^{n}W_k(\lfloor n/d\rfloor)=(n)_k\implies W_k(n)=\sum_{d=1}^{n}\mu(d)\big(\lfloor n/d\rfloor\big)_k$$ by Möbius inversion (for computing, it may be preferable to use the first of these equalities, as a recurrence relation for $$O(\sqrt{n})$$ needed values of $$W_k$$, rather than the last formula; see the bottom of this answer for details).