Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.