13
$\begingroup$

I want to find this

$ \sum_{k=1}^n \gcd(k,n)$

but I don't know how to solve. Does anybody can help me to finding this problem.

Thanks.

  • 0
    n $\leq$ 200000. Ok I will read Euler's totient function.2012-04-22

1 Answers 1

19

This is Pillai's arithmetical function as in OEIS A018804

Formulae given there include $\sum_{d|n} d \,\phi(n/d)$ and $\sum_{d|n} d \, \tau(d) \, \mu(n/d)$ where $\phi(n)$ is Euler's totient function, $\tau(n)$ is the number of divisors and $\mu(n)$ is the Möbius function.