Recursively counting divisors of a number I want to make a recursive function f that counts all (not only prime) different divisors of a given natural number:
$f(n): = |{a ∈ ℕ | ∃ b ∈ ℕ : a . b = n }| $ ; with $ f(0)=0 $ 
for example $ f(3) = 2$,  $f(6) = 4$,  $f(16) = 5 $ etc.
Theoretically, how could I do that? 
Thanks.
 A: *

*If $n=1$, then return $1$.

*Find the smallest divisor of $n$. It is a prime. Call it $p$.

*Find the largest power $p^e$ that divides $n$.

*Return $(e+1)\cdot f(\dfrac{n}{p^e})$
A: You need to use the Möbius function $\mu(n)$:
Recurrence:
Let $z=1$
$$T(n, k) = \text{ if } k = 1 \text{ then }  1 - \sum_{i=2}^{i=n} \mu(i) \frac{T(n, i)}{i^{(s - 1)}} \text{ else }  
  \text{ if } \text{mod(n, k)} = 0 \text{ then } T(n/k, 1) \text{ else } 0 \text{ else } 0.$$
Then:
$$\lim\limits_{s \rightarrow z} T(n,1) = \text{number of divisors of n}$$
The first few entries of the matrix $T$ then starts:
$$T=\left(
\begin{array}{cccccccccccc}
 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\
 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &  \\
 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &  \\
 3 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &  \\
 2 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &  \\
 4 & 2 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 &  \\
 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 &  \\
 4 & 3 & 0 & 2 & 0 & 0 & 0 & 1 & 0 & 0 & 0 &  \\
 3 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 &  \\
 4 & 2 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 1 & 0 &  \\
 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 &  \\
 \vdots &  &  &  &  &  &  &  &  &  &  &  \ddots
\end{array}
\right)$$
which has the number of divisors tau A000005 recursively defined in the first column, starting:
$$\text{A000005} = 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, ...$$
As a Mathematica 8 program this recurrence is:
(*recurrence*)
Clear[t, s, n, k, z, nn];
z = 1;
nn = 12; t[n_, k_] := 
 t[n, k] = 
  If[k == 1, 1 - Sum[MoebiusMu[i] t[n, i]/i^(s - 1), {i, 2, n}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; A = 
 Table[Table[Limit[t[n, k], s -> z], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]

