Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.