¿Existe una fórmula recursiva para la función Totiente de Euler

Question

He estado buscando una fórmula recursiva para la función totiente de Euler o la función mu de Möbius para utilizar estas relaciones e intentar crear una función generadora para estas funciones aritméticas.

Answer 1

La respuesta a tu pregunta depende de lo que entiendas por "función generadora". Supongo que el tipo de función generadora que tienes en mente es una función generadora ordinaria, que toma la forma de una serie de potencias. Estas funciones generadoras funcionan mejor con secuencias que satisfacen aditivo fórmulas recursivas; el ejemplo clásico son los números de Fibonacci, que satisfacen la recurrencia $F_{n+2}=F_{n+1}+F_n$ . Pero la función de Möbius y la función totiente son fundamentalmente multiplicativas, y no creo que la función generadora ordinaria de ninguna de ellas tenga una expresión sencilla de forma cerrada.

Hay al menos dos alternativas a las funciones generadoras ordinarias que dan buenos resultados para la $\mu$ y $\varphi$ funciones. La primera es una Serie de Dirichlet que tiene la forma $$f(s)=\sum_{n=1}^\infty \frac{a_n}{n^s}.$$ Resulta que la serie de Dirichlet para $\mu$ es $$\frac{1}{\zeta(s)} = \sum_{n=1}^\infty \frac{\mu(n)}{n^s}$$ y la serie de Dirichlet para $\varphi$ como mencionó Brad, es $$\frac{\zeta(s-1)}{\zeta(s)} = \sum_{n=1}^\infty \frac{\varphi(n)}{n^s}.$$ Aquí $\zeta(s)$ es el famoso Función zeta de Riemann .

El segundo tipo útil de función generadora es una Serie Lambert que tiene la forma $$f(q) = \sum_{n=1}^\infty a_n\frac{q^n}{1-q^n}.$$ La serie Lambert para $\mu$ y $\varphi$ son particularmente simples; están dadas por $$\sum_{n=1}^\infty \mu(n)\frac{q^n}{1-q^n} = q$$ y $$\sum_{n=1}^\infty \varphi(n)\frac{q^n}{1-q^n} = \frac{q}{(1-q)^2}.$$

Answer 2

Recurrencia para la función totiente de Euler: $$\phi(n) = n-{\sum_{d|n}}_\limits{d<n} \phi(d)$$

Recurrencia para la función de Möbius: $$\mu(n) = -{\sum_{d|n}}_\limits{d<n} \mu(d)$$

Recurrencia para la función de von Mangoldt: $$\Lambda(n) = \log(n)-{\sum_{d|n}}_\limits{d<n} \Lambda(d)$$

Para la recurrencia de la inversa de Dirichlet de la función totiente de Euler: $$a(n) = \frac{1}{n}-{\sum_{d|n}}_\limits{d<n} a(d)$$ hay que multiplicar el resultado por $n$ .

Mathematica 8:

(*Recursive formula for Eulers totient function:*)
(*Mathematica*)
Clear[t];
t[1, 1] = 1;
t[n_, k_] := 
 t[n, k] = 
  If[k == 1, n - Sum[t[n, k + i], {i, 1, n - 1}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]
MatrixForm[Table[Table[t[n, k], {k, 1, 12}], {n, 1, 12}]]

---

(*Recursive formula for the Möbius function:*)
(*Mathematica*)
(*start*)
Print["Möbius function:"];
 Clear[t, s, n, k, z];
 z = 1;
 nn = 12;
t[1, 1] = 1;
t[n_, k_] := 
 t[n, k] = 
  If[k == 1, -Sum[t[n, k + i]/(i + 1)^(s - 1), {i, 1, n - 1}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; MatrixForm[
 Table[Table[Limit[t[n, k], s -> z], {k, 1, nn}], {n, 1, nn}]] (*end*)

Véase también esta respuesta: https://math.stackexchange.com/a/164829/8530

Recurrence for the Möbius function for complex numbers:
(*start*)Print["Möbius function:"]
Clear[t, s, n, k, z];
z = ZetaZero[-1];
nn = 12;
t[1, 1] = 1;
t[n_, k_] := 
 t[n, k] = 
  If[k == 1, -Sum[t[n, k + i]/(i + 1)^(s - 1), {i, 1, n - 1}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; MatrixForm[
 A = Table[
   Table[Limit[t[n, k], s -> z], {k, 1, nn}], {n, 1, nn}] (*end*)]

Clear[t, s, n, k, z];
nn = 12;
z = ZetaZero[1];
MatrixForm[
 B = Table[
   Table[If[n >= k, If[Mod[n, k] == 0, MoebiusMu[n/k]*(n/k)^z, 0], 
     0], {k, 1, nn}], {n, 1, nn}]]
N[A - B]
(*program end*)

---

Print["compared to:"];
z = N[ZetaZero[1]]; 
N[Table[MoebiusMu[n]*n^z, {n, 1, 12}]]

Si buscas la función generadora ordinaria de la función de Möbius, esto es lo más parecido que puedes conseguir:

$$\sum_{n=1}^\infty \mu(n)x^n = x - \sum_{a=2}^\infty x^{a} + \sum_{a=2}^\infty \sum_{b=2}^\infty x^{ab} - \sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty x^{abc} + \sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty \sum_{d=2}^\infty x^{abcd} - \cdots$$

Lo escribí en Wikipedia. Función Möbius

s = 1;
Table[-Total[
   MoebiusMu[
     Divisors[n][[1 ;; Length[Divisors[n]] - 1]]]/(Divisors[n][
       1 ;; Length[Divisors[n]] - 1])^(s - 1)], {n, 1, 42}]

Answer 3

Hay 2 recursividades paramétricas para la función Mobius. Por favor, mire el https://oeis.org/A266378

La fórmula real no es muy sencilla. Sea

$$T(m,n) = \begin{cases} 1, & m=1, n=1 \\ 0, & m=1, n \ne 1 \\ T(m, n-1) + T(m-1, n) - T(m-1, n-m), & m \ne 1 \end{cases} .$$

Con la ayuda de $T$ definiremos $a$ por

$$a(n,m) = a(n, m-1)+a(n-1, m)-a(n-1, m-n+1)-\\ a\Big(n-1, \nu(n-1)\Big) \Big(T(n-2, m-1)-T(n-2, m-2)\Big),$$

donde $\nu(n)=\dfrac {(n-2)(n-3)} 2$ , $a(n,0)=-1$ y $a(n,m)=0$ para $\nu(n)<m<0$ .

Con estos preparativos tenemos $\mu(n) = a(n,\nu(n))$ la función de Möbius.

EDITADO: Hay una fórmula muy parecida para la función Totiente de Euler: http://oeis.org/A282283

$$H(n,m) = \begin{cases} 1, & m=0, n=1 \\ 0, & m \ne 0, n=1 \\ H(n - 1, n*(n - 1)/2 - m)*(-1)^n - H(n - 1, m), & n > 1 \end{cases} .$$ $$Q(n, m) = H(n, m - 2) - 2*H(n, m - 1) + H(n, m)$$ Y luego: $$b(n,m) = b(n - 1, m - n + 1) - b(n - 1, m) - b(n - 1, \nu(n - 1))*Q(n - 1, m))$$ donde $\nu(n)=\dfrac {(n*(n-3)+4)} 2$ . Con estos preparativos tenemos $\phi(n) = b(n,\nu(n))$ la función Totient.

Answer 4

Hay dos fórmulas recursivas sencillas que se pueden utilizar para calcular $\mu(n)$ y $\varphi(n)$ en $[1,N]$ :

$$\sum_{k=1}^n \mu(k) \lfloor n/k\rfloor= 1, \qquad \quad\sum_{k=1}^n \varphi(k) \lfloor n/k\rfloor= \frac{n(n+1)}{2}$$

después de $\sum_{d | n} \mu(d)=1_{n= 1}$ y $\sum_{d | n} \varphi(d) = n$