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

Leave a comment

10 * 2