1
$\begingroup$

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

  • 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).2012-08-31

2 Answers 2

4

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

  • 0
    @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).2012-08-31
7

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.

  • 0
    @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.2015-04-12