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.

Does there exist a recursive function, or a recurrence relation, for the number-of-divisors function?

For example, something like this:

$\sigma_0(n) = \sigma_0(n-1) + \sigma_0(n-2)$

share|improve this question
    
Often a recursive function means the same thing as a computable function. Clearly, the number of divisor function would be computable. –  William Aug 31 '12 at 6:03
1  
I doubt there will be one which you would find satisfying. For example, $n$ can have pretty arbitrary divisors with $n+1$ prime, and vice-versa (I think). –  Alex Becker Aug 31 '12 at 6:06

2 Answers 2

up vote 3 down vote accepted

It's multiplicative, so if $m,n$ are coprime, that is have gcd 1, then $\sigma(mn) = \sigma(m) * \sigma(n)$.

share|improve this answer
    
Could this be similar to the totient function which also has this property? Can I also say $\sigma(mn) = \sigma(m) * \sigma(n) * \frac{gcd(mn)}{\sigma(gcd(mn))}$? As per here: en.wikipedia.org/wiki/… –  Khaled Aug 31 '12 at 8:26
    
Khaled, have you tried it for small values of $m$ and $n$ to see whether it is plausible? –  Gerry Myerson Aug 31 '12 at 13:07
    
@GerryMyerson Yes and it didn't work (I tried 72 = 12*6), but I'm sure there must be a similar property since they are both multiplicative functions (I hope so anyway). –  Khaled Aug 31 '12 at 14:53

I don't know about the number-of-divisors function, but Euler found a very nice recurrence for the sum-of-divisors function, which you can find here. A more recent treatment is here. See also John A. Ewell, Recurrences for the Sum of Divisors, Proceedings of the American Mathematical Society, Vol. 64, No. 2 (Jun., 1977), pp. 214-218.

The Euler recurrence is $$\sigma(n)=\sigma(n-1)+\sigma(n-2)-\sigma(n-5)-\sigma(n-7)+\sigma(n-12)+\sigma(n-15)-\dots$$ where the numbers $1,2,5,7,12,15,\dots$ are the "pentagonal numbers" $k(3k\pm1)/2$.

EDIT: The above formula isn't quite right when $n$ itself is a pentagonal number, in fact I think it's off by $n$. I'll try to find the time to edit in the precise correction (if someone else doesn't get there first).

share|improve this answer
    
And this will not work for the number-of-divisors function? –  Khaled Aug 31 '12 at 14:54
    
Have you tried it? –  Gerry Myerson Sep 1 '12 at 1:08

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.