The divisor function represented as $d(n)$ counts the number of a divisors of an integer

example: $d(18)$

The numbers that divide $18$ are $1, 2, 3, 6, 9, 18$ then $d(18) = 6$

## Important observations

• if $p$ is a prime number then $d(p) = 2$, also $d(p^k) = k + 1$ because every power of $p$ is a divisor of $p^k$, e.g. $p^0, p^1, p^2, \ldots, p^k$
• if $n$ is a product of two distinct primes, say $n = pq$ then $d(pq) = d(p) \cdot d(q)$, also $d(p^iq^j) = d(p^i) \cdot d(q^j)$
• in general let $n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_n^{a_n}$ then $d(n) = d(p_1^{a_1}) \cdot d(p_2^{a_2}) \cdot \ldots \cdot d(p_n^{a_n})$ where $p_i$ is a prime factor that divides $n$

example: $d(18)$

\begin{align*} d(18) &= d(3^2 \cdot 2) \\ &= d(3^2) \cdot (2) \\ &= 3 \cdot 2 \\ &= 6 \end{align*}
int number_of_divisors(int n) {
int total = 1;
for (int i = 2; i * i <= n; i += 1) {
int power = 0;
while (n % i == 0) {
power += 1;
n /= i;
}
total *= (power + 1);
}
if (n > 1){
total *= 2;
}
}


## Sum of divisors

The sum of divisors is another important quantity represented by $\sigma_k(n)$, it’s the sum of the $k$-th powers of the divisors of $n$

$$\sigma_k(n) = \sum_{d|n} d^k$$

examples:

\begin{align*} \sigma_0(18) &= 1^0 + 2^0 + 3^0 + 6^0 + 9^0 + 18^0 \\ &= 1 + 1 + 1 + 1 + 1 \\ &= 6 \end{align*}

So when $k = 0$ the sum of divisors ($\sigma_0{n}$) function is equal to $d(n)$, i.e. $\sigma_0(n)$ gives the number of divisors of $n$

another example:

\begin{align*} \sigma_1(18) &= 1^1 + 2^1 + 3^1 + 6^1 + 9^1 + 18^1 \\ &= 1 + 2 + 3 + 6 + 9 + 18 \\ &= 39 \end{align*}

when $k = 1$ we actually get the function we expect (a function which sums the divisors)

### Important observations

• if $p$ is a prime number then $\sigma(p) = 1 + p$ since the only divisors of a prime number are $1$ and $p$
• if $p$ is a prime number then $\sigma(p^k) = 1 + p + p^2 + \ldots + p^k$ because every power of $p$ is a divisor of $p^k$, e.g. $p^0, p^1, p^2, \ldots, p^k$

Consider

$$$$\label{sigma-p-k} \sigma(p^k) = 1 + p + p^2 + \ldots + p^k$$$$

multiplying the expression by $p$ we have

$$$$\label{sigma-p-k-times-p} p \cdot \sigma(p^k) = p + p^2 + p^3 + \ldots + p^{k + 1}$$$$

subtracting \eqref{sigma-p-k} from \eqref{sigma-p-k-times-p}

$$p \cdot \sigma(p^k) - \sigma(p^k) = p^{k + 1} - 1$$

factoring $\sigma(p^k)$

$$\sigma(p^k) (p - 1) = p^{k + 1} - 1$$

hence

$$\sigma(p^k) = \frac{p^{k + 1} - 1}{p - 1}$$
• if $p$ is a product of two distinct primes say $n = pq$ then $\sigma(pq) = \sigma(p) \cdot \sigma(q)$, also $\sigma(p^iq^j) = \sigma(p^i) \cdot \sigma(q^j)$

• in general let $n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_n^{a_n}$ then $\sigma(n) = \sigma(p_1^{a_1}) \cdot \sigma(p_2^{a_2}) \cdot \ldots \cdot \sigma(p_n^{a_n})$ where $p_i$ is a prime factor that divides $n$

example: $\sigma(18)$

\begin{align*} \sigma(18) &= \sigma(3^2 \cdot 2) \\ &= \sigma(3^2) \cdot \sigma(2) \\ &= \frac{3^3 - 1}{3 - 1} \cdot \frac{2^2 - 1}{2 - 1} \\ &= 13 \cdot 3 \\ &= 39 \end{align*}
int sum_of_divisors(int n) {
int total = 1;
for (int i = 2; i * i <= n; i += 1) {
if (n % i == 0) {
int primePower = i;
while (n % i == 0) {
primePower *= i;
n /= i;
}
// sigma(n^k) = (n^{k + 1} - 1) / (k - 1)
total *= (primePower - 1) / (i  - 1);
}
}
if (n > 1) {
// if n is still a prime number after factorization
// sigma(n) = 1 + n
total *= (1 + n);
}