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)$
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)$
It's multiplicative, so if $m,n$ are coprime, that is have gcd 1, then $\sigma(mn) = \sigma(m) * \sigma(n)$.
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).
EDIT2: Here is a link to replace the dead one. Also, one has to make the convention that $\sigma(n-n)=n$ to make the formula work when $n$ is a pentagonal number.