Sum of Divisors Function - Euler's recursion

Number theory has many functions that are based on the arithmetical properties of a given input integer $n$. These functions are called number-theoretic functions. Well known examples are, e.g., the Euler's Totient Function and The Möbius Function. Since arithmetical properties often depend in one or the other way on the integer's prime factorization, these functions are usually hard to compute for large integers due to the factorization problem. One of these functions, that heavily depends on that factorization, is the Divisor Function.

Definition [Divisor Function] Given an integer $n$ then the divisor function $\sigma_k(n)$ is defined as $$ \sigma_k(n) := \sum_{d|n}d^k$$

Hence, $\sigma_0(n)$ is equal to the number of divisors of an integer and $\sigma_1(n)$ is equal to the sum of all divisors of $n$. E.g. $\sigma_1(15) = 1 + 3 + 5 + 15 = 24$.

Figure 1. Example plot of the divisor function (Source: Wikipedia)

In order to compute this function one obviously needs to know the prime factors of $n$. Surprisingly, this function can be defined recursively, as proved by Leonard Euler.

[Euler: Divisor Function - recursive] - Informal. Given an integer $n$ then the divisor function $\sigma_1(n)$ can be defined as $$\small{ \sigma_1(n) = \sigma_1(n-1)+\sigma_1(n-2)-\sigma_1(n-5)-\sigma_1(n-7)+\sigma_1(n-12)+\sigma_1(n-15)-... }$$ If the input gets negative you stop. If the input gets zero, then $\sigma_1(0) = n$.

The integers that are subtracted, i.e., $1,2,5,7,12,15,...$ are the generalized pentagonal numbers. They are defined as $$ p(i) = \frac{3i^2-i}{2}$$ and the terms in the recursion are obtained by entering the values $0, -1, 1, -2, 2, -3, 3, ...$. One could write the recursion as $$\sigma_1(n) = \sum^{b_1}_{i=1} (-1)^{i+1}\sigma_1(n-p(i)) + \sum^{b_2}_{i=1} (-1)^{i+1}\sigma_1(n-p(-i))$$, whereof $b_1$ is the unique integer such that $n-p(b_1+1) < 0 \leq n-p(b_1)$ and $n-p(-(b_2+1)) \leq 0 < n-p(-b_2)$. Note, that these are efficiently computable, via solving a simple quadratic equation. Furthermore, as long as $n = d_1d_2$ and $p$ and $q$ are co-prime divisors we have $$\sigma_1(n) = \sigma_1(d_1d_2) = \sigma_1(d_1)\sigma_1(d_2)$$.

If $n = pq$ with $p,q$ primes, the information $$\sigma_1(n) = 1+ p + q + n = (p+1)(q+1)$$ is already enough to factor $n$. It is $$\varphi(n) = (p-1)(q-1) = pq-p-q+1$$ hence, $$\varphi(n)+2(p+q) = \sigma_1(n)$$ From the point of view of a cryptographer, it seems a little bit strange, that one compute a function that reveals the factors of a certain integer $n$, only by the means of smaller integers, which might be easier to factorize. However, the total number of smaller integers that need to be factorized in this case is sufficiently large. So a direct approach to compute $\sigma_1(n)$ via that recursion is negligible. But are there any other valueable information that can be deduced from this recursion formula?

The value of $\sigma_1(n)$ is clearly always positive. The recursion, which is an alternating sum, must pick exactly those integers, that the final value is positive. If you, for example, pick $n = 35$, then you have
\begin{align*}
\small{\sigma_1(35)} = & \small{\sigma_1(34)+\sigma_1(33)-\sigma_1(30)-\sigma_1(28)+\sigma_1(23)+\sigma_1(20)-\sigma_1(13)-\sigma_1(9)+\sigma_1(0)}\\
= & \small{54 + 48 - 72 - 56 + 24 + 42 - 14 - 13 + 35 }\\
= & \small{48}
\end{align*} Partial sums can and are indeed negative.