Divisor function

The divisor function $\sigma_k(n) = \sum_{d \mid n} d^k$ adds up the $k$-th powers of the divisors of $n$. Two cases do almost all the work: $\sigma_0(n) = d(n)$ (also written $\tau(n)$), which counts the divisors, and $\sigma_1(n) = \sigma(n)$, which sums them. Its relative $s(n) = \sigma(n) - n$, the sum of the proper divisors, sits behind perfect, abundant and amicable numbers. The function keeps coming back in the problems below because it is the simplest arithmetic quantity that depends on a number's factorisation rather than its size: 48 has ten divisors and 47 has two. Asked about divisors, the useful question is never "what are they?" but "what is the factorisation?". Once the factorisation is in hand, the formula does the rest.

The idea: one formula, from the factorisation

The divisors of $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$ are exactly the numbers $p_1^{b_1} \cdots p_r^{b_r}$ with $0 \le b_i \le a_i$. Each exponent is chosen independently, so both the count and the sum split prime by prime:

$$d(n) = \prod_i (a_i + 1), \qquad \sigma_k(n) = \prod_i \left(1 + p_i^k + p_i^{2k} + \dots + p_i^{a_i k}\right) = \prod_i \frac{p_i^{(a_i+1)k} - 1}{p_i^k - 1}.$$

This is the statement that $\sigma_k$ is a multiplicative function: $\sigma_k(mn) = \sigma_k(m)\,\sigma_k(n)$ whenever $\gcd(m, n) = 1$. Each prime-power factor is a geometric series. Nearly every problem on this page uses that identity in one of four ways.

1. Split a number into coprime parts. Problem 12 wants the first triangular number $T_i = i(i+1)/2$ with more than 500 divisors. Consecutive integers are coprime, so once the factor of 2 is assigned to whichever of $i$ or $i+1$ is even, $d(T_i)$ is the product of two divisor counts on numbers about $\sqrt{2T_i}$ in size, not one count on $T_i$:

if i % 2 == 0:
    divisor_count = num_factors(i // 2) * num_factors(i + 1)
else:
    divisor_count = num_factors(i) * num_factors((i + 1) // 2)

2. Turn a counting question into $d$ of something. The equation $\tfrac1x + \tfrac1y = \tfrac1n$ of problems 108 and 110 rearranges to $(x - n)(y - n) = n^2$. Its solutions are therefore the factor pairs of $n^2$, and there are $\lceil d(n^2)/2 \rceil$ of them up to order. Because $d(n^2) = \prod (2a_i + 1)$, "at least $N$ solutions" becomes a condition on an exponent vector, and the search runs over exponent shapes, not over $n$: the smallest $n$ for a shape puts the largest exponents on the smallest primes. Several of the geometry problems tagged here (176, 827) take the same route once a Pythagorean or Diophantine parametrisation reduces them to counting divisors.

3. Invert the formula: from a divisor count back to shapes. $d(k) = 8$ means $\prod (a_i + 1) = 8$, and the factorisations $8 = 4 \cdot 2 = 2 \cdot 2 \cdot 2$ give exactly three disjoint shapes, $p^7$, $p^3 q$ and $pqr$. That decomposition is the whole combinatorial content of problem 501; what is left is prime counting at scale. Problem 500 runs the same inversion the other way: the smallest number with $2^{500500}$ divisors is built greedily from factors $p^{2^j}$, each of which doubles the count, always taking the smallest one available. The inversion also works on a congruence rather than an exact count. Problem 641 asks for which $k$ the count $d(k) \equiv 1 \pmod 6$. Oddness forces $k = m^2$ (divisors pair up as $e, k/e$, and only a square has an unpaired one), so $d(k) = \prod (2a_i + 1)$ again. Each factor is $0$, $1$ or $-1$ modulo 3 according to $a_i \bmod 3$, so the condition becomes a rule on exponent residues. That rule describes the numbers $m = c^3 q^2$ with $q$ square-free and having an even number of prime factors, and from there the problem is a lattice count over $(c, q)$ using the Möbius function.

4. Reason about $\sigma$ one prime power at a time. Divisibility and ratio conditions on $\sigma$ factor too. A prime $q$ divides $\sigma(n)$ exactly when it divides some $\sigma(p^a) = 1 + p + \dots + p^a$, which is how problem 565 reduces "2017 divides $\sigma(i)$" to conditions on the individual prime powers of $i$. The abundancy index $\sigma(n)/n = \prod \sigma(p^a)/p^a$ is a product of factors each strictly greater than 1, so problem 241 searches factorisations depth-first and prunes as soon as the running ratio can no longer reach its target. Problem 650 never builds its astronomically large product of binomials: it tracks the prime-exponent vector with Legendre's formula and evaluates $\sigma$ as one geometric series per prime. Problem 675 combines that with an incremental update. Its function $\sum_{d \mid n} 2^{\omega(d)}$ is $2e + 1$ on $p^e$, so it is $d(n^2)$ in disguise, and it is wanted for every factorial $i!$ up to $10^7$. Going from $(i-1)!$ to $i!$ changes only the exponents of the primes dividing $i$. The product is therefore carried forward: divide out each old factor $2e' + 1$ (by a modular inverse) and multiply in the new $2e + 1$. That is at most $\omega(i)$ ratios per step, rather than one factor for every prime up to $i$.

Computing it for every $n$ at once

When a problem needs $d(n)$ or $\sigma(n)$ for all $n$ up to a bound, factoring each number separately is the slow path. A divisor-sum sieve turns the question around: rather than asking which numbers divide $n$, let each $i$ add itself to every one of its multiples. Problem 95 does this for $s(n)$, the proper-divisor sum (21 and 23 are the small versions of the same loop):

for i in range(1, max_num // 2 + 1):
    for j in range(i * 2, max_num + 1, i):
        divisor_sum[j] += i

The cost is $\sum_i N/i = O(N \log N)$ additions, with no divisions or factorisation at all. Add 1 instead of i and the same loop gives $d(n)$; add i * i and it gives $\sigma_2(n)$, which is problem 211 over 64 million values. Two refinements are worth knowing:

Pair the divisors. Each divisor $a < \sqrt n$ comes with a partner $n/a$, so a sieve can walk only $a \le \sqrt N$ and credit both members of the pair. Problem 179 counts the $n < 10^7$ with $d(n) = d(n+1)$ this way.
Sieve the multiplicative way. A linear sieve visits each $n$ once, through its smallest prime factor. If it also records that prime's exponent, it can update $d$ or $\sigma$ with the multiplicative formula in $O(N)$.

Summing it without listing it

Some problems want $\sum_{n \le N} \sigma_k(n)$ for $N$ far too large for any sieve (problems 401 and 439 have this shape). The way out is to swap the order of summation. Every $d \le N$ divides exactly $\lfloor N/d \rfloor$ of the numbers up to $N$, so

$$\sum_{n \le N} \sigma_k(n) = \sum_{d \le N} d^k \left\lfloor \frac{N}{d} \right\rfloor.$$

The quotient $\lfloor N/d \rfloor$ takes only $O(\sqrt N)$ distinct values, so the sum groups into blocks of constant quotient, each block's $\sum d^k$ given by a closed form (see the floor function and the divisor summatory function). The Dirichlet hyperbola method is the general version of this trick. The terms $(d, q)$ with $dq \le N$ are lattice points under a hyperbola. Each one has $d \le \sqrt N$ or $q \le \sqrt N$, so you sum the column strip, add the row strip, and subtract the $\sqrt N \times \sqrt N$ square that both strips counted. Problem 401 does exactly this for $\sigma_2$, where a row's weight is the square pyramidal number $x(x+1)(2x+1)/6$. The cost drops from $O(N \log N)$ to $O(\sqrt N)$, which is the difference between impossible and instant at $N = 10^{15}$.

The swap works because $\sigma_k$ is a convolution of two functions with easy prefix sums. When the function is only known to be multiplicative, sum it with a Min_25 sieve instead. Problem 452 counts ordered $n$-tuples with product at most $m$, which is $\sum_{k \le m} d_n(k)$ for the $n$-fold divisor function $d_n$. The per-prime formula still holds. Distributing an exponent $e$ over $n$ slots is stars and bars, so $d_n(p^e) = \binom{n+e-1}{e}$, and $d_n(p) = n$ is constant on primes. That is enough for the sieve: it takes prime counts at the $O(\sqrt m)$ floor values $\lfloor m/i \rfloor$ and builds up the composites one smallest prime factor at a time, in roughly $O(m^{3/4})$ total.

How to reason about it

Factorisation first. If a statement mentions divisors, look for the prime-power form. A condition on $d(n)$ is a condition on the exponents, and a condition on $\sigma(n)$ usually splits into one condition per prime power.
Know the sizes. $d(n)$ grows very slowly: the most divisors below $10^7$ is 448 and below $10^{18}$ it is 103680 (the highly composite numbers hold these records). $\sigma(n)$, by contrast, is about $n$ on average and never much more than a small multiple of it ($\sigma_2(n) < \zeta(2)\,n^2$), so check whether your 64-bit integers survive before you pick a type.
Divide before you reduce. Closed-form block sums carry denominators like 2 and 6. If the modulus shares a factor with them (problem 401 works modulo $10^9$), there is no modular inverse. Divide the factors that are exact multiples first, then reduce each factor and multiply.
One number, many numbers, or a sum? Trial division to $\sqrt n$ is fine for a handful of values. Use a sieve for every value up to $N$. For an aggregate over a range too large to sieve, use the swapped sum. Picking the wrong one of these three costs orders of magnitude.
Proper or not. $s(n)$ leaves out $n$ itself and $\sigma(n)$ includes it, and amicable, perfect and abundant are all defined with $s$. Mixing them up is the most common off-by-$n$ bug on this page.
Divisor variants. Unitary and bi-unitary divisors (problem 861) change the per-prime-power factor but keep the multiplicative structure, so the same reasoning carries over with a different local formula.

Problems23 / 43

● 0012 — Highly Divisible Triangular Number
● 0021 — Amicable Numbers
● 0023 — Non-Abundant Sums
● 0095 — Amicable Chains
● 0108 — Diophantine Reciprocals I
● 0110 — Diophantine Reciprocals II
● 0153 — Investigating Gaussian Integers
● 0157 — Base-10 Diophantine Reciprocal
● 0176 — Common Cathetus Right-angled Triangles
● 0179 — Consecutive Positive Divisors
● 0211 — Divisor Square Sum
● 0241 — Perfection Quotients
○ 0378 — Triangle Triples
○ 0379 — Least Common Multiple Count
● 0401 — Sum of Squares of Divisors
● 0420 — $2 \times 2$ Positive Integer Matrix
○ 0439 — Sum of Sum of Divisors
● 0452 — Long Products
○ 0474 — Last Digits of Divisors
● 0485 — Maximum Number of Divisors
○ 0500 — Problem 500!!!
● 0501 — Eight Divisors
○ 0548 — Gozinta Chains
● 0561 — Divisor Pairs
● 0565 — Divisibility of Sum of Divisors
○ 0598 — Split Divisibilities
○ 0608 — Divisor Sums
○ 0636 — Restricted Factorisations
● 0641 — A Long Row of Dice
○ 0646 — Bounded Divisors
● 0650 — Divisors of Binomial Product
● 0675 — $2^{\omega(n)}$
○ 0699 — Triffle Numbers
○ 0722 — Slowly Converging Series
○ 0723 — Pythagorean Quadrilaterals
○ 0735 — Divisors of $2n^2$
○ 0738 — Counting Ordered Factorisations
○ 0827 — Pythagorean Triple Occurrence
○ 0840 — Sum of Products
○ 0861 — Products of Bi-Unitary Divisors
● 0883 — Remarkable Triangles
○ 0920 — Tau Numbers
○ 0956 — Super Duper Sum