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 ?
Is there an iterative formula for the function $d(n)$?
-
0@Haile for all n
– 2012-12-03
1 Answers
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.