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

If you set $k=0$, $\sigma_0(n)$ is equal to the number of divisors of an integer. For $k=1$ you get that $\sigma_1(n)$ is equal to the sum of all divisors of $n$. E.g. $\sigma_1(15) = 1 + 3 + 5 + 15 = 24$.

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

Definition: Divisor Function - recursive (Informal)

Given an integer $n$ then the divisor function $\sigma_1(n)$ [sum of divisors] 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 $d_1$ and $d_2$ 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 = 5\cdot 7$, 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*}

Although the final result is positive, several partial sums are negative — illustrating how delicately the recursion balances its terms. Euler’s recursion does not give a practical way to compute $\sigma_1(n)$ for large $n$, but it reveals a remarkable structural fact: arithmetic information that seems to require factorization can sometimes be encoded entirely through additive relations among smaller integers. Understanding why this works remains as interesting as the formula itself.

Related Posts:

• An explicit formula for discrete logarithms
• The magic constant 0x5f3759df