

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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|cite|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
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
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|cite|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:… – 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|cite|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
the "more recent treatmen" is a dead link. – darij grinberg Apr 11 '15 at 20:12
@darij, yes, I noticed that yesterday, but wasn't able to find whatever it was that I linked to in 2012. But typing "pentagonal number formula" into the Internet should turn up no shortage of discussions of the formula. – Gerry Myerson Apr 12 '15 at 0:27

Your Answer


