Divisor function ($\tau (n)$)

The divisor function $\tau (n)={\sum }_{d\mid n}1$ counts the positive integer divisors of a positive integer $n$. In particular $\tau (1)=1$, because $1$ has just one positive integer divisor. More generally the notation ${\sigma }_k(n)={\sum }_{d\mid n}{d}^k$ gives $\tau ={\sigma }_0$ and the sum-of-divisors function ${\sigma }_1$. Thus the divisor function counts the positive integer divisors, while ${\sigma }_1$ adds their sizes. ^[ref]

If the prime factorization is $n={\prod }_{k=1}^r{p}_k^{a_k}$ with distinct prime numbers $p_k$ and positive exponents $a_k$, thenThe short proof is a count: each positive integer divisor has a unique form ${\prod }_{k=1}^r{p}_k^{b_k}$, where $0\le b_k\le a_k$. There are $a_k+1$ choices at each prime number, and choosing them gives every positive integer divisor exactly once. For $n=1$ there are no prime factors and the product is $1$.

For $12=2^2\cdot 3$, choose $i\in \{0,1,2\}$ and $j\in \{0,1\}$ to obtain $2^i{3}^j$. The six values are $1,2,4,3,6,12$; sorted, the positive integer divisors are $1,2,3,4,6,12$. Therefore $\tau (12)=(2+1)(1+1)=6$. The diagram makes the independent exponent choices visible.

This count is useful because a known prime factorization gives $\tau (n)$ without testing every smaller positive integer for divisibility. It also proves the divisor function is a multiplicative function: coprime integers have disjoint prime factors, so their exponent choices combine. For example $\tau (6)=4=\tau (2)\tau (3)$, but $\tau (4)=3\ne 4=\tau (2{)}^2$, so it is not a completely multiplicative function. Equivalently, $\tau =1\ast 1$ under Dirichlet convolution, counting ordered pairs of positive integers whose product is $n$.

Factor a positive integer while multiplying the exponent-plus-one contributions to its divisor count. After removing all prime factors below the current trial factor, a trial factor that divides the remainder must itself be prime. Remove its full power and advance. Once the trial factor's square exceeds the remainder, any remainder greater than one is prime and contributes a factor two. The invariant separates the original integer into removed prime powers and the remaining coprime factor; no factor array is necessary.

A positive integer whose divisor count strictly exceeds that of every smaller positive integer. A record scan maintains the largest earlier value of the divisor function and emits exactly candidates exceeding it. Equality does not create a new record; the first candidate is handled by a zero initial record.

The ratio of the sum of the positive divisors of a positive integer to that integer. For coprime $a,b$, the ratio is multiplicative because the divisor function $\sigma$ is multiplicative. The contribution of a prime power $p^e$ is $(1+p+\cdots +p^e)/p^e$, so a prescribed quotient can be searched through its remaining numerator and denominator.

Two distinct positive integers $a,b$ are amicable when the sum of the proper divisors of $a$ is $b$ and the sum of the proper divisors of $b$ is $a$. The pair $220,284$ is an example. Iterating the proper-divisor sum can also produce longer directed cycles.

A pair of distinct positive integers in which each is the proper-divisor sum of the other. The integers $220$ and $284$ form an amicable pair.

For each $\eta >0$, the divisor function satisfies the displayed bound. Write $n=\prod p^{a_p}$, so $\tau (n)=\prod (a_p+1)$. For all sufficiently large primes, $a+1\le 2^a\le p^{\eta a}$ for every $a\ge 0$. For each of the finitely many smaller primes, ${\sup }_{a\ge 0}(a+1)p^{-\eta a}$ is finite. Multiplying these finitely many constants proves the bound. Products of a fixed number of divisor functions obey the same conclusion after reducing $\eta$.

The divisor function satisfies ${\sum }_{n\le X}d(n{)}^2\ll X{\log }^3(2X)$. Partial summation consequently gives ${\sum }_{n\le X}d(n{)}^2/n\ll {\log }^4(2X)$.