Robert Eisele
Systems Engineer, Architect and DBA

# Calculate the sum of divisors

Let's say you have an arbitrary number $$n\in \mathbb{N}$$. If you want to calculate the sum of it's divisors, you would come up with a loop which is $$O(n)$$. Here is how you can make it much faster.

Let $$\delta(n)$$ be the number of divisors and $$\sigma(n)$$ the sum of the divisors of number $$n$$. For any prime $$p$$, it's obvious that $$\sigma(p)=p+1$$, as it's only divisors can be $$1$$ and $$p$$. If you go ahead, it's also obvious that $$\delta(p^a)=a+1$$, and:

$\begin{array}{rl}\sigma(p^a) &= \prod\limits_{i=0}^{\delta(p^a)}p^i \\&= 1 + p + p^2 + ... + p^a \\p\sigma(p^a) &= p + p^2 + p^3 + ... + p^{a+1} \\p\sigma(p^a) - \sigma(p^a) &= p + p^2 + p^3 + ... + p^{a+1} - (1 + p + p^2 + ... + p^a) \$$p - 1) \sigma(p^a) &= p^{a+1}-1 \\\sigma(p^a) &= \frac{p^{a+1}-1}{p-1}\end{array}$ We now use the multiplicativity property of \(\sigma$$, which means that $$\sigma(x\cdot y\cdot ...)=\sigma(x)\cdot\sigma(y)\cdot...$$ with $$x, y, ...$$ relatively prime and can say that

$\begin{array}{rl}\sigma(n) &= \sigma(p_1^{a_1} \cdot p_2^{a_2} \cdot ...) \\&= \sigma(p_1^{a_1}) \cdot \sigma(p_2^{a_2}) \cdot ...\\&= \frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdot... \\&= \prod\limits_{i=1} \frac{p_i^{a_i+1}-1}{p_i-1}\end{array}$

## Calculate sum of divisors from 1 to n

If we go even further and wonder what $$\Delta(n) = \sum\limits_{i=1}^n \sigma(i)$$ is, we can do much better, without factorization. Let's say that $$\phi(i,j) = \begin{cases} 1, & \text{if}\ i|j \\ 0, & \text{else} \end{cases}$$, then

$\begin{array}{rl}\Delta(n) &= \sum\limits_{i=1}^n \sigma(i)\\&= \sum\limits_{j=1}^n \sum\limits_{i=1}^n i \cdot \phi(i,j)\\&= \sum\limits_{i=1}^n \sum\limits_{j=1}^n i \cdot \phi(i,j)\\&= \sum\limits_{i=1}^n i \cdot \sum\limits_{j=1}^n \phi(i,j)\\&= \sum\limits_{i=1}^n i \lfloor\frac{n}{i} \rfloor \\&= n^2 - \sum\limits_{i=1}^n mod(n, i)\end{array}$

You might also be interested in the following