The divisor function represented as $d(n)$ counts the number of 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;
  }
  return total;
}

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

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

multiplying the expression by $p$ we have

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

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);
  }
  return total;
}