# Is there an iterative formula for the function $d(n)$?

Is there an iterative formula for the function $d(n)$ ?
While d(n) is the count of divisors for n
For example in Euler's totient function $\phi(nm)= \phi(n)\phi(m) . \frac{d}{\phi(d)}$ where $d=gcd(m,n)$
so using memorization we can iterate on a big number to get the result of $\phi$ without the need of factoring it for example :
to calculate $\phi(12)$ we first make a list of primes then start a trial division process on that list obviously 2|12 so we perform
$\phi(6 * 2)= \phi(2)\phi(6) . \frac{2}{\phi(2)}$ from that we get $\phi(12)= 1*\phi(6)*2$ since $\phi(p) = p-1$
then we call the function again for $\phi(6)$ and after that we save the result of 12 for later calculations of of it is multiples : $\phi(12*m)= \phi(12)\phi(m) . \frac{d}{\phi(d)}$
so is the same thing possible for $d(n)$ ? is there a similar formula that can break a big number n into smaller parts then calculate those parts ?

-
This may be of some help: en.wikipedia.org/wiki/Divisor_function – Shaun Ault Dec 1 '12 at 14:31
not really the only thing there was when n = p*q (both primes)which is :$\sigma(n)=n+1+q+p$ – Loers Antario Dec 1 '12 at 15:51
You want $\sigma_0(n)$, not $\sigma(n)$. The former is the number of divisors of $n$. The latter should probably have been $\sigma_1(n)$ in the Wikipedia article... – Shaun Ault Dec 1 '12 at 17:32
@LoersAntario do you need to compute d(n) for a single n? Or for all n < K, K fixed? – Haile Dec 1 '12 at 20:41
@Haile for all n<k – Loers Antario Dec 3 '12 at 17:41

First, the divisor function $d(n)$ is multiplicative on coprime factors. That is: $$d(mn) = d(m)d(n), \quad \textrm{if}\; gcd(m,n) = 1.$$ To see this is true, consider the prime factorization of $mn = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$. Without loss of generality, we may assume that $m = p_1^{e_1} \cdots p_t^{e_t}$ and $n = p_{t+1}^{e_{t+1}}\cdots p_k^{e_k}$. Here we used $gcd(m,n)=1$ to ensure that no $p_i$ is common to both expressions.
Since any factor must have a prime factorization $p_1^{e'_1}p_2^{e'_2} \cdots p_k^{e'_k}$ with each $e'_i \leq e_i$, we see that every factor of $mn$ is uniquely determined as a product of factors of $m$ and $n$ respectively. Then we observe that for $p$ prime, $d(p^e) = e+1$.
This provides a very implementable recursive formula for $d(N)$, as long as you can ensure that when you write $N=mn$, you have $gcd(m,n) = 1$. The base cases are the powers of primes.