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