Dado N, ¿cuál es el valor de [matemáticas] \ sum_ {k = 1} ^ {N} \ frac {k} {gcd (k, N)} [/ matemáticas]?

Answer 1

Digamos que escribimos [math] \ sum_ {k = 1} ^ {N} \ frac {k} {\ gcd (k, N)} [/ math] reemplazando [math] k [/ math] con [math] Nk [/ math] para obtener

[matemáticas] \ sum_ {k = 1} ^ {N} \ frac {N – k} {\ gcd (N – k, N)} [/ matemáticas]

y como [math] gcd (N – k, N) = \ gcd (k, N) [/ math] nos damos cuenta de que nuestra respuesta es

[matemáticas] \ frac {N} {2} \ sum_ {k = 1} ^ {N} \ frac {1} {\ mcd (k, N)} [/ matemáticas].

Ahora, tratemos de encontrar [math] \ sum_ {k = 1} ^ {N} \ frac {1} {\ gcd (k, N)} [/ math].

Podemos escribirlo como [matemáticas] \ sum_ {g | N} ^ {} \ varphi (\ frac {N} {g}) * \ frac {1} {g} [/ math],
porque [math] \ varphi (\ frac {N} {g}) [/ math] básicamente cuenta cuántos elementos entre 1 y [math] N [/ math] tienen un mcd con [math] N [/ math] igual a [matemáticas] g [/ matemáticas].

Ahora, puede reemplazar fácilmente [matemática] g [/ matemática] por [matemática] \ frac {N} {g} [/ matemática] en la ecuación anterior para obtener [matemática] \ frac {1} {N} \ sum_ {g El | N} ^ {} \ varphi (g) * g [/ math].

Por lo tanto, atravesamos todos los factores de [matemáticas] N [/ matemáticas] y calcular [matemáticas] \ varphi (N) [/ matemáticas] incluso para grandes [matemáticas] N [/ matemáticas] es fácil usar propiedades.

Answer 2

  n = int (input ("Ingrese n-value")) # ingrese el valor de n
 N = n
 suma = 0
 para i en rango (1, N + 1):
   m = i
   N = n
   mientras que (N% m! = 0):
     si (N