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;
  }
  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;
}