Recursive number of divisors function

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)$

-
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
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
add comment

2 Answers

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

-
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
add comment

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).

-
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
add comment