Estoy tratando de resolver este problema, la parte más importante de este problema es encontrar ?$$\sum_{i = 1}^{n} \frac{n}{\gcd(i, n)}$$
Donde $n$ $10^{12}$
Respuesta
¿Demasiados anuncios?
Deje $C(n)$ ser su suma, considere la posibilidad de un divisor fijo $d$$n$; aparecerá en el denominador siempre $i$ es un múltiplo de a $d$ $i/d$ es coprime con $n/d$ que es exactamente $\varphi(n/d)$ veces por lo que la suma puede ser escrito como $$ C(n) = \sum_{d \vert n} \frac{n}d \varphi(n/d) = \sum_{d \vert n} d \varphi(d) $$ Donde la suma es sobre los divisores positivos de $n$ $\varphi(n)$ representa (El de Euler totient función).
Es fácil probar que la función de $C(n)$ es multiplicativa (como lo es cualquier función de la forma $\sum_{d\vert n} f(n)$ al $f(n)$ es una función multiplicativa), así que usted puede escribir como $$\begin{aligned} C(n) &= \prod_{p^\alpha \vert\vert n} C(p^\alpha) \\ &=\prod_{p^\alpha \vert\vert n} \sum_{d \vert p^\alpha} d\varphi(d)\\ &=\prod_{p^\alpha \vert\vert n} \sum_{j=0}^\alpha p^j \varphi(p^j)\end{aligned} $$ donde el producto es más de la máxima primer poderes dividiendo $n$. pero $\varphi(p^j) = p^j(1-1/p) $, por lo que $$ C(n) = \prod_{p^\alpha \vert\vert n}\left( 1+\sum_{j=1}^\alpha (p^{2j}-p^{2j-1})\right) $$ la suma en el interior del producto es: $$ 1 - p + p^2 - p^3 +- \dots + p^{2\alpha} = \frac{p^{2\alpha+1}+1}{p+1} $$ Y así $$ \sum_{i=1}^n \frac{n}{\gcd(i,n)} = \prod_{p^\alpha\vert\vert n} \frac{p^{2\alpha+1}+1}{p+1} $$
