Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.

The answer to your question depends on what you mean by "generating function". I expect that the type of generating function you have in mind is an ordinary generating function, which takes the form of a power series. Such generating functions work best with sequences that satisfy additive recursive formulas; the classic example is the Fibonacci numbers, which satisfy the recurrence $F_{n+2}=F_{n+1}+F_n$. But the Möbius function and the totient function are fundamentally multiplicative, and I do not imagine that the ordinary generating function for either of them has any simple closed-form expression.

There are at least two alternatives to ordinary generating functions which yield nice results for the $\mu$ and $\varphi$ functions. The first is a Dirichlet series, which has the form $$ f(s)=\sum_{n=1}^\infty \frac{a_n}{n^s}. $$ It turns out that the Dirichlet series for $\mu$ is $$ \frac{1}{\zeta(s)} = \sum_{n=1}^\infty \frac{\mu(n)}{n^s} $$ and the Dirichlet series for $\varphi$, as Brad mentioned, is $$ \frac{\zeta(s-1)}{\zeta(s)} = \sum_{n=1}^\infty \frac{\varphi(n)}{n^s}. $$ Here $\zeta(s)$ is the famous Riemann zeta function.

The second useful type of generating function is a Lambert series, which has the form $$ f(q) = \sum_{n=1}^\infty a_n\frac{q^n}{1-q^n}. $$ The Lambert series for $\mu$ and $\varphi$ are particularly simple; they are given by $$ \sum_{n=1}^\infty \mu(n)\frac{q^n}{1-q^n} = q $$ and $$ \sum_{n=1}^\infty \varphi(n)\frac{q^n}{1-q^n} = \frac{q}{(1-q)^2}. $$

Recurrence for the Euler totient function: $$\phi(n) = n-{\sum_{d|n}}_\limits{d<n} \phi(d)$$

Recurrence for the Möbius function: $$\mu(n) = -{\sum_{d|n}}_\limits{d<n} \mu(d)$$

Recurrence for the von Mangoldt function: $$\Lambda(n) = \log(n)-{\sum_{d|n}}_\limits{d<n} \Lambda(d)$$

For the recurrence for the Dirichlet inverse of the Euler totient function: $$a(n) = \frac{1}{n}-{\sum_{d|n}}_\limits{d<n} a(d)$$ you need to multiply the result with $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*)

See also this answer: 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}]]

If you are looking for the ordinary generating function for the Möbius function then this is the closest you can get:

$$\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$$

I wrote it into Wikipedia. Möbius function

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

There is 2 parametric recursion for the Mobius function. Please look at the https://oeis.org/A266378

The actual formula is not very simple. Let

$$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} .$$

With the aid of $T$ we shall define $a$ by

$$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), $$

where $\nu(n)=\dfrac {(n-2)(n-3)} 2$, $a(n,0)=-1$ and $a(n,m)=0$ for $\nu(n)<m<0$.

With these preparations we have $\mu(n) = a(n,\nu(n))$, the Möbius function.

EDITED: There is very similiar formula for the Euler Totient function: 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)$$ And then: $$b(n,m) = b(n - 1, m - n + 1) - b(n - 1, m) - b(n - 1, \nu(n - 1))*Q(n - 1, m))$$ where $\nu(n)=\dfrac {(n*(n-3)+4)} 2$. With these preparations we have $\phi(n) = b(n,\nu(n))$, the Totient function.

Is there a recursive formula for Euler's Totient function

Related

Recent Posts