i-1-n-j-1-n-gcd-i-j-1-D-1-D-is-ture-0-D-is-false-

Question Number 196062 by qaz last updated on 17/Aug/23

\underset{i = 1}{\sum^{n}} \underset{j = 1}{\sum^{n}} [g c d (i, j) = 1] = ?, [D] = {\begin{cases} 1, D i s t u r e . \\ 0, D i s f a l s e . \end{cases}

Commented by mr W last updated on 17/Aug/23

i {d o n}^{'} t t h i n k w e c a n g e t i t i n a c l o s e d

f o r m .

n = 10 : \Rightarrow 63

n = 100 : \Rightarrow 6087

n = 1000 : \Rightarrow 808383

Answered by witcher3 last updated on 17/Aug/23

A_{n} = \sum_{i, j ⩽ n} [\gcd (i, j) = 1]

A_{n + 1} = \sum_{i, j ⩽ n + 1} [\gcd (i, j) = 1]

= A_{n} + 2 \underset{m = 1}{\sum^{n + 1}} [\gcd (n + 1, m)]

= A_{n} + 2 φ (n + 1) . . φ euler indecatrice function

φ (n) = card (i, \gcd (i, n) = 1)

\Rightarrow A_{n + 1} - A_{n} = 2 φ (n + 1)

\Rightarrow \underset{k = 1}{\sum^{n - 1}} A_{k + 1} - A_{k} = 2 \underset{k = 1}{\sum^{n - 1}} φ (k + 1), n ⩾ 2

\Rightarrow A_{n} - A_{1} = 2 \underset{k = 1}{\sum^{n - 1}} φ (k)

A_{n} = 1 + 2 \underset{k = 1}{\sum^{n - 1}} φ (k)

Facebook Tweet Pin