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,\dots ,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^i{q}^j)=d(p^i)\cdot d(q^j)$
• in general, let $n=p_1^{a_1}\cdot p_2^{a_2}\cdot \dots \cdot p_n^{a_n}$, then $d(n)=d(p_1^{a_1})\cdot d(p_2^{a_2})\cdot \dots \cdot d(p_n^{a_n})$ where $p_i$ is a prime factor that divides $n$.

example: $d(18)$

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$

Examples:

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:

when $k=1$, we actually get the function we expect (a function that 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+\dots +p^k$ because every power of $p$ is a divisor of $p^k$, e.g., $p^0,p^1,p^2,\dots ,p^k$.

Consider

Multiplying the expression by $p$, we have

Subtracting $\text{(1)}$ from $\text{(2)}$

Factoring $\sigma (p^k)$

hence

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

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

example: $\sigma (18)$

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