Sum of Divisors

For a positive integer \(n\), the sum-of-divisors function adds every positive divisor of \(n\):

\[ \sigma(n)=\sum_{d\mid n}d. \]

For example, the divisors of \(12\) are \(1,2,3,4,6,12\), so \(\sigma(12)=28\). The divisor pairs explain why trial division never has to pass \(\sqrt n\).

Prime Powers

If \(p\) is prime, the positive divisors of \(p^a\) are exactly

\[ 1,p,p^2,\ldots,p^a. \]

Their sum is a finite geometric series:

\[ \begin{aligned} \sigma(p^a)&=1+p+p^2+\cdots+p^a,\\ p\sigma(p^a)&=p+p^2+\cdots+p^{a+1},\\ (p-1)\sigma(p^a)&=p^{a+1}-1. \end{aligned} \]

Therefore

\[ \boxed{\sigma(p^a)=\frac{p^{a+1}-1}{p-1}}. \]

Use Multiplicativity

The function \(\sigma\) is multiplicative: if \(\gcd(m,n)=1\), then \(\sigma(mn)=\sigma(m)\sigma(n)\). To see why, every divisor of \(mn\) is uniquely a product of one divisor of \(m\) and one divisor of \(n\).

By the fundamental theorem of arithmetic, write

\[ n=\prod_{i=1}^{k}p_i^{a_i}. \]

The prime powers are pairwise coprime, hence

\[ \boxed{ \sigma(n)=\prod_{i=1}^{k}\frac{p_i^{a_i+1}-1}{p_i-1} }. \]

For \(12=2^2\cdot3\), this gives

\[ \sigma(12)=(1+2+2^2)(1+3)=7\cdot4=28. \]

The sum of the proper divisors excludes \(n\) itself and is therefore \(s(n)=\sigma(n)-n\). This quantity classifies positive integers as deficient, perfect, or abundant.

Exact JavaScript Implementation

JavaScript Number values cease to represent every integer above \(2^{53}-1\). The implementation uses BigInt throughout, factors out \(2\), then tries odd candidates only. It accumulates each geometric sum directly, avoiding exponentiation and division.

function sumOfDivisors(n) {
  if (typeof n !== "bigint" || n < 1n) {
    throw new TypeError("n must be a positive BigInt");
  }

  let remaining = n;
  let result = 1n;

  for (let prime = 2n; prime * prime <= remaining; prime = prime === 2n ? 3n : prime + 2n) {
    if (remaining % prime !== 0n) {
      continue;
    }

    let primePower = 1n;
    let geometricSum = 1n;
    do {
      remaining /= prime;
      primePower *= prime;
      geometricSum += primePower;
    } while (remaining % prime === 0n);

    result *= geometricSum;
  }

  if (remaining > 1n) {
    result *= remaining + 1n;
  }

  return result;
}

The worst case is a prime \(n\), which requires trial candidates up to \(\sqrt n\). For many repeated queries, a sieve of smallest prime factors moves that work into a reusable precomputation.

Summatory Divisor Function

Now consider the sum of all divisor sums through \(N\):

\[ S(N)=\sum_{n=1}^{N}\sigma(n). \]

Instead of factoring every integer, reverse the order of summation. A positive integer \(d\) contributes once for each multiple of \(d\) not exceeding \(N\), and there are \(\lfloor N/d\rfloor\) such multiples:

\[ \begin{aligned} S(N) &=\sum_{n=1}^{N}\sum_{d\mid n}d\\ &=\sum_{d=1}^{N}d\left\lfloor\frac{N}{d}\right\rfloor. \end{aligned} \]

An \(O(N)\) loop follows immediately, but the quotient \(q=\lfloor N/d\rfloor\) assumes only \(O(\sqrt N)\) distinct values. If an interval begins at \(l\), the same quotient continues through

\[ r=\left\lfloor\frac{N}{q}\right\rfloor. \]

The contribution of the complete interval is

\[ q\sum_{d=l}^{r}d =q\left(T(r)-T(l-1)\right), \qquad T(x)=\frac{x(x+1)}{2}. \]

function summatorySumOfDivisors(n) {
  if (typeof n !== "bigint" || n < 1n) {
    throw new TypeError("n must be a positive BigInt");
  }

  const triangular = value => value * (value + 1n) / 2n;
  let total = 0n;
  let left = 1n;

  while (left <= n) {
    const quotient = n / left;
    const right = n / quotient;
    total += quotient * (triangular(right) - triangular(left - 1n));
    left = right + 1n;
  }

  return total;
}

For \(N=4\), the values are \(\sigma(1)=1\), \(\sigma(2)=3\), \(\sigma(3)=4\), and \(\sigma(4)=7\), so \(S(4)=15\). The grouped algorithm obtains the same exact result without factoring any of the four integers separately.

Complexity

• Testing every possible divisor of one \(n\): \(O(n)\).
• Pairing divisors or trial-factorizing one \(n\): \(O(\sqrt n)\) arithmetic steps in the worst case.
• Computing \(S(N)\) with quotient grouping: \(O(\sqrt N)\) groups and \(O(1)\) auxiliary storage.

These bounds count arithmetic operations. With arbitrarily large integers, the cost of each multiplication, division, and remainder also grows with the bit length of its operands.