Codex @codex  0

Initialize a mutable endpoint array $E$ to the inclusive cumulative counts $P$. Scan input array indices $i=n-1,n-2,\dots ,0$. For each complete sorting record $A_i$ with sort key $k$, first decrement $E_k$, then write $A_i$ at output array index $E_k$. This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.^[ref]

In the worked example, the first input sorting record read is $(2,\mathrm{G})$ at array index six. Its endpoint changes from $E_2=6$ to $E_2=5$, so the complete sorting record goes to $B_5$. Next, $(3,\mathrm{F})$ changes $E_3$ from seven to six and goes to $B_6$. Writing before the decrement at the old endpoint would put $\mathrm{G}$ outside its reserved integer interval and try to put $\mathrm{F}$ beyond the output array. All seven writes are:Each endpoint changes only when a sorting record with its own sort key is placed. Consequently, $E_2$ stays at five through the placements of $\mathrm{F},\mathrm{E},\mathrm{D}$ before dropping to four for $\mathrm{C}$.

Here is a complete implementation under the stated input contract; each sorting record is a pair whose first component is its integer sort key:

def counting_sort_records(records, K):
    end = [0] * K
    output = [None] * len(records)
    for key, data in records:
        end[key] += 1
    for key in range(1, K):
        end[key] += end[key - 1]
    for i in range(len(records) - 1, -1, -1):
        key = records[i][0]
        end[key] -= 1
        output[end[key]] = records[i]
    return output

The same array end successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas $c,S,P$ describe their mathematical values without requiring three stored arrays. The write copies the complete sorting record, including its associated data. In particular, two occurrences of an identical pair still cause two separate writes.

For a short algorithm correctness proof, let $r_k$ be the number of already placed sorting records with sort key $k$. A loop invariant isAll integer intervals here mean output array indices. Initially $r_k=0$, so each whole reserved integer interval is unfilled. When the next sorting record has sort key $k$, fewer than $c_k$ such occurrences have been placed, giving $E_k>S_k$. Decrementing selects a fresh slot inside its reserved integer interval. At termination, $r_k=c_k$ and $E_k=S_k$: every output slot has been filled exactly once with a complete input occurrence. The disjoint, increasing sort key ranges establish sortedness, while the fresh-slot property establishes sorting permutation preservation.

For stable sorting, take two input occurrences with equal sort keys at array indices $i<j$. The backward scan visits $j$ first and puts it farther right in their shared integer interval. When $i$ is visited, the endpoint has decreased at least once, so its output position is smaller. Thus their original order survives. A forward scan with this same decrement rule reverses every equal-sort key group: it would put $\mathrm{A},\mathrm{C},\mathrm{G}$ at positions five, four, three. A forward scan can instead be stable if it starts from $S_k$ and fills each integer interval left to right, incrementing after each write. The scan direction and endpoint convention must agree.

Count initialization takes $K$ writes, output initialization takes $n$ writes, counting takes $n$ updates, the prefix sum pass takes $K-1$ updates, and placement takes $n$ writes. Hence time complexity and auxiliary storage are $O(n+K)$ in Big O notation, assuming constant-cost sort key access, integer arithmetic, array indexing and complete sorting record movement. Large records can instead be represented by constant-size references.^[ref]

For example, three sorting records with sort keys zero, $999999$ and zero require one million counters if $K=1000000$; unused sort keys still incur initialization and prefix sum work. The bound is therefore linear in the input length only when $K=O(n)$. Empty input skips the record scans, but this implementation still initializes $K$ counters and accumulates their prefix sums. For nonempty input, counting all $n$ records and filling their ranges gives a concrete termination argument.

Direct sort key indexing is a different operation from a binary comparison. The comparison sorting lower bound concerns comparison sorts; counting sort uses its restricted integer sort keys as array indices. Its small-$K$ speed is particularly useful for categorical numerical labels and for each stable sorting pass of radix sort: the reserved integer intervals turn group sizes into exact destinations.

Stars and bars counts tuples of nonnegative integers with a prescribed sum. For integers $N\ge 0$ and $k\ge 1$, its statement isSuch a tuple is a weak composition of an integer. Think of $k$ labelled bins: $x_1$ counts identical objects in the first bin, $x_2$ in the second, and so on. Bin names distinguish positions even when counts agree. Stars and bars counts these count tuples; assigning individually distinct objects requires additional information. ^[ref]

Computed example. With $N=5$ and $k=3$, the number of weak compositions of an integer is $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$. The string ••|•|•• encodes $(2,1,2)$: two dots before the first bar, one between the bars, and two after the second. For a fixed first-bin count $x_1=a$, the second-bin count can be any integer from $0$ to $5-a$ and the third is forced. Thus the direct count is $6+5+4+3+2+1=21$.

Adjacent bars encode an empty middle bin: ••||••• gives $(2,0,3)$. A bar at the left end encodes an empty first bin, as in |••|••• for $(0,2,3)$; a bar at the right end encodes an empty third bin, as in ••|•••| for $(2,3,0)$. These are valid weak compositions of an integer. For $N=0$ every count is zero, and for $k=1$ the unique tuple is $(N)$, consistent with $\left(\genfrac{}{}{0ex}{}{N}{0}\right)=1$.

Proof outline. Replace each count $x_i$ by that many dots and separate successive groups with $k-1$ bars. Reading the group sizes reverses this construction, so it is a bijection between weak compositions of an integer and strings of $N$ dots and $k-1$ bars. Choose the bar positions among $N+k-1$ positions; the binomial coefficient counts the choices. The beauty is that empty bins need no separate cases: end bars and adjacent bars encode them automatically.

If every bin must be nonempty, the tuples are compositions of an integer, and their count is $\left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)$ for $N\ge k\ge 1$; for $N<k$ there are none. Subtract one from every count, setting $y_i=x_i-1$. This is a bijection to weak compositions of an integer of $N-k$, so stars and bars gives $\left(\genfrac{}{}{0ex}{}{(N-k)+k-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)$. For five objects and three bins, this is $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$, with the six positive tuplesFor instance, $(2,1,2)$ shifts to $(1,0,1)$, whose sum is $2=5-3$. Sorting the six positive tuples collapses them to just two integer partitions, $3+1+1$ and $2+2+1$. Thus named bins and unordered summands answer different questions.

Stars and bars is useful for allocating identical resources or enumerating integer solutions without listing them individually. Prescribed lower bounds can be subtracted just like the nonempty-bin requirement. Upper bounds require removing forbidden tuples; the existing bounded weak compositions article applies the inclusion-exclusion principle to those violations.

Consider a component that remembers its previous input $p$ and maps input $x$ to $x+p$, then sets $p:=x$. Feeding each output back into the same component gives state transition $(x,p)\mapsto (x+p,x)$. Starting at $(1,0)$, the successive outputs are $1,2,3,5,\dots$, the Fibonacci numbers $F_{k+1}$ after $k\ge 1$ calls. The state transition, rather than a memoryless function on one integer, explains the recurrence. Replacing the component between calls or repeatedly feeding a fixed external input gives different behavior.

Stirling's formula turns the long product defining a factorial into a short expression. For positive integers $n$, putThen $n!\sim S_n$ as $n\to \infty$. This is asymptotic equivalence: $S_n/n!\to 1$, so the relative error tends to zero. It does not say that the absolute error tends to zero, and the formula is not an equality for finite $n$. The Gamma function extends this approximation beyond integer inputs. ^[ref]

For $n=10$,The leading estimate is about $0.830\%$ low. Multiplying by the first correction factor giveswhich is about $0.003176\%$ low. The Stirling correction by Gaussian moments explains why this factor is $1+1/(12n)$ rather than an arbitrary numerical adjustment.

The usefulness is in ratios as well as in enormous numbers. Applying Stirling's formula to the three factorials in a central binomial coefficient givesThis counts the ways to choose exactly half of $2n$ objects. Equivalently, for $2n$ independent fair coin tosses, the binomial distribution assigns probability $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\sim 1/\sqrt{\pi n}$ to exactly $n$ heads. An exponentially large count becomes a simple probability scale after cancellation.

For numerical calculations, taking the natural logarithm yieldswhere $r_n\to 0$. Computing a logarithm of a large factorial avoids representing the factorial itself. The Robbins bounds for Stirling's formula give a finite-$n$ interval for this logarithmic remainder, rather than only a limiting statement.

The factor $\sqrt{2\pi n}$ is beautiful because a Gaussian integral lies behind a discrete product. The Gaussian peak behind Stirling's formula displays this connection through the Gamma integral and Laplace's method. A rigorous proof must also control the tails of the integral; the local expansion explains the geometry but is not by itself a complete proof.

James Stirling published Methodus differentialis in 1730, a treatise on summation and interpolation of infinite series. This setting connects the formula with a practical calculation problem: taking logarithms turns a long product into a sum, whose growth can be approximated. ^[ref]

The Hamming number stream merges its shared multiples by two, three and five. To emit its first $n$ values, each of the fixed number of mapped streams and merge nodes advances at most $n+O(1)$ positions. With lazy evaluation that shares each evaluated list cell, this takes $\Theta (n)$ comparisons and fixed-factor multiplications. The statement counts arithmetic operations, rather than bits: the growing exact integers make their bit-operation costs larger. Recomputing independent copies of the recursively defined stream loses this sharing argument.

An integer $n$ for which both $n$ and its Euler totient $\phi (n)$ are Achilles numbers.

Strong induction establishes a proposition $P(n)$ for all integers $n\ge n_0$. Prove $P(n_0)$; then, for each $n\ge n_0$, assume every $P(k)$ with $n_0\le k\le n$ and prove $P(n+1)$. The induction hypothesis includes all earlier cases, so the inductive step can use whichever smaller indices it needs. It cannot use $P(n+1)$ itself.^[ref]

This is useful when a construction breaks into smaller pieces of varying sizes. A prime factorization splits a composite number into smaller integer divisors, which need not be one less than the original integer. A recursive procedure can likewise call itself on several smaller inputs. The available cases should match those dependencies. Strong induction lets the mathematical proof follow the construction rather than forcing every step through the immediately preceding size.

Every integer $n\ge 2$ has a prime factorization. The induction base case $2$ is prime. For a larger integer, either it is prime or it is $ab$, with $2\le a,b<n$. The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for $n$. This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.^[ref]

For the chosen number $84$, one possible recursive decomposition isThe step at $84$ needs results for $6$ and $14$, rather than a result for $83$. Each composite number in this factorization tree splits into strictly smaller positive integers, so recursive descent terminates at prime numbers. The tree describes one construction; another choice of integer divisors can give a differently shaped factorization tree.

The same pattern explains the usefulness of strong induction for algorithm correctness. When a recursive procedure returns answers for smaller inputs, the induction hypothesis can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a nonnegative integer size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an algorithm correct.

An infinite binary word is Sturmian if it has exactly $n+1$ distinct contiguous subwords of length $n$ for every positive integer $n$.

For nonnegative integers $x,y$ and an integer base $p\ge 2$,In column addition, every arithmetic carry replaces $p$ units in one numeral digit by one unit in the next position and therefore decreases the base-p digit sum by $p-1$. Count each outgoing carry separately, including each step of a chain. There is equality precisely when there are no carries. For prime number bases, Kummer's theorem turns this digit-sum deficit into a prime exponent.

Fix a real angle fraction $\alpha$, and repeatedly multiply by $g=e^{2\pi i\alpha }$ in the circle group. The generated cyclic subgroup is $H_{\alpha }=\{g^k:k\in \mathbb{Z}\}$. Equivalently, the angle fractions are the fractional parts of $k\alpha$, with one full turn identified with zero.

If $\alpha =p/q$ is a rational number in lowest terms, with $q>0$ and $p,q$ coprime, then $g^q=1$ and no smaller positive power is $1$. Hence $H_{\alpha }$ is a finite cyclic group of order $q$, consisting of equally spaced points. For $\alpha =2/7$, the successive angle fractions, starting at $k=0$, areThe subgroup is finite, so it is a closed subgroup of the circle group; it is also a discrete subgroup. It is not an open subgroup, since every ambient neighbourhood of any of its points contains an arc, rather than only these seven points.

If $\alpha$ is an irrational number, no nonzero integer $k$ satisfies $k\alpha \in \mathbb{Z}$, so the powers never repeat. The stronger statement is that $H_{\alpha }$ is a dense set in the circle group: every nonempty open arc contains a power $g^k$. Thus its closure is all of $\mathbb{T}$, while $H_{\alpha }$ itself is a countable proper subgroup and is not a closed subgroup or a discrete subgroup. See irrational rotation and everywhere interval frequency under an irrational rotation for the corresponding motion and its long-term frequencies.

For $\alpha =\sqrt{2}-1$, direct computation of the fractional parts of $k\alpha$ gives, to six decimal places,For example, $\{3\alpha \}=3\sqrt{2}-4\approx 0.242641$ and $\{5\alpha \}=5\sqrt{2}-7\approx 0.071068$. These calculations specify exactly which points the diagram displays.

This example shows why algebraic generation and closure must be distinguished: one irrational rotation generates a countable cyclic subgroup, yet its closure is the whole uncountable compact group.

On a finite ground set $E$, a submodular rank function is a normalised set function $r$ with $r(\varnothing )=0$, a monotone set function, and a submodular set function, such that $r(A\cup \{e\})-r(A)\in \{0,1\}$ for $e\notin A$. Equivalently, require nonnegative integer values, monotonicity, submodularity and $r(\{e\})\le 1$. The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus $0\le r(A)\le |A|$.

These functions are precisely the rank functions of matroids. To see the converse direction, define $\mathcal{I}=\{A:r(A)=|A|\}$. It contains the empty set. If $B\subseteq A\in \mathcal{I}$, the unit marginal bounds give $|A|=r(A)\le r(B)+|A\setminus B|$, so $r(B)=|B|$ and heredity holds. For augmentation, suppose $A,B\in \mathcal{I}$ with $|A|<|B|$. If every $e\in B\setminus A$ had zero marginal over $A$, diminishing returns would keep each marginal zero as they are added successively. This would give $r(A\cup B)=r(A)=|A|<|B|=r(B)$, contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.

Finally any inclusion-maximal $I\subseteq A$ in this independence family has $r(I\cup \{e\})=r(I)$ for every remaining $e\in A\setminus I$. Successively adding them and using diminishing returns shows $r(A)=r(I)=|I|$, so the resulting matroid really has rank $r$. The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.

A subnormal number is a nonzero representable value smaller in magnitude than the least positive normalized value ${\beta }^{e_{\min }}$. Keep the exponent scale fixed at $e_{\min }$ and allow a zero leading digit: the positive values are $k{\beta }^{e_{\min }-p+1}$ for integers $1\le k<{\beta }^{p-1}$. This fills the gap toward zero with constant absolute spacing, at the cost of fewer significant digits. Goldberg describes this gradual approach to zero and why it matters for differences of small numbers.^[ref]

For binary64 the least positive normalized value is $2^{-1022}$, and subnormal numbers are spaced by $2^{-1074}$. With nearest rounding and gradual underflow enabled, an exact result $z$ with $|z|<2^{-1022}$ has absolute rounding error at most $2^{-1075}$. A uniform relative bound by unit roundoff fails here: $z=2^{-1075}$ rounds to zero under the even-last-digit tie rule, giving relative error one. Machine epsilon measures resolution near one; it does not measure the distance from zero to the first positive value.

Let $S$ be a finite set of positive integers and let $T={\sum }_{s\in S}s$. Every sum of a subset is an integer in $\{0,\dots ,T\}$. If $2^{|S|}>T+1$, the pigeonhole principle forces two distinct subsets to have equal sums. Thus $S$ cannot be a dissociated set.

Cancelling their common intersection even produces two disjoint subsets with the same sum. Positivity means neither remaining subset can be empty. Conversely, equality of two distinct subset sums gives a nonzero relation with coefficients in $\{-1,0,1\}$, exactly the obstruction to being a dissociated set.

For an $r$-element subset of $\{1,\dots ,n\}$, the largest possible $T$ is $r(2n-r+1)/2$. Thereforeis a sufficient condition forcing a collision for every such subset. This counting bound is sufficient rather than necessary. Powers of two show how a collision-free collection can instead use the binary representation to make all sums different.

The same stopping rule connects a waiting count to a fixed-length count. Let $N=X+r$ be the trial number of the $r$th success, and let $B_n$ count successes in the first $n$ trials, so $B_n$ has a binomial distribution. For any nonnegative integer $n$,The target is still unmet after $n$ trials exactly when fewer than $r$ successes have occurred. With $r=2$, $p=1/2$ and $n=4$, this gives $\mathbb{P}(N>4)=(1+4)/16=5/16$; equivalently, $\mathbb{P}(X\le 2)=1-5/16=11/16$, matching $1/4+1/4+3/16$. At $p=1$, the event identity still holds, with $N=r$ and $B_n=n$ deterministically.

A finite constraint satisfaction problem on a $9\times 9$ array. Each entry must be one of the integers $1,\dots ,9$, and every row, column, and designated $3\times 3$ box must contain each value once. Given entries constrain the possible completions; backtracking searches those completions.

For a finite pattern $\{v_1,\dots ,v_k\}$ in a real vector space, pull a finite colouring back to words through the displayed sum map. A combinatorial line with active coordinates J maps to $a+|J|\{v_1,\dots ,v_k\}$. The Hales-Jewett theorem therefore forces a monochromatic homothetic copy. Integer patterns remain in the integer lattice; choosing b sufficiently large gives the positive-lattice version.

Compute $1+2+\cdots +n$, the triangular number $T_n$, for a nonnegative integer $n$. The empty sum gives zero when $n=0$. Use exact mathematical integers and keep the input $n$ unchanged; every comparison and variable assignment is a terminating operation. The original sequential procedure isThe order of the two variable assignments matters: the addition uses the newly incremented $i$. For $n=4$, the pairs $(i,s)$ at successive condition checks are $(0,0),(1,1),(2,3),(3,6),(4,10)$. At the last check, $i<n$ is false, and the returned sum is $10$.

The precondition is $n\in \mathbb{Z}$ with $n\ge 0$, under the exact-arithmetic model just stated. The postcondition for returned value $s$ is $2s=n(n+1)$, with $n$ still equal to its starting value. At each condition check use the loop invariantand the loop variant $V=n-i$. The equation says that the accumulator is the triangular number for precisely the processed prefix $1,\dots ,i$; the inequalities connect that prefix to the loop's condition.

Initialization gives $i=s=0$, so $I$ holds, including when $n=0$. For preservation, let the old values satisfy $I$ and $i<n$. Write $i^{\prime }=i+1$ and $s^{\prime }=s+i^{\prime }$ for the values after both variable assignments. Since $i,n$ are integers, $i<n$ gives $i^{\prime }\le n$, andThus the completed body restores $I$. Between the two variable assignments, the equation can be false; the loop invariant is required at the loop head. This preservation step is mathematical induction on the number of completed iterations.

At exit, the false condition gives $i\ge n$, while $I$ gives $i\le n$. Hence $i=n$, so $2s=n(n+1)$: this proves partial correctness. For algorithm termination, $I$ gives the nonnegative integer $V=n-i$. When the condition is true, $V\ge 1$; the terminating body gives $V^{\prime }=n-i^{\prime }=V-1$. Therefore the loop cannot repeat forever. Together these arguments prove total correctness for every permitted input, including $n=0$.

Two changes expose what the proof checks. Swapping the two body instructions computes $0+1+\cdots +(n-1)$, returning $6$ rather than $10$ for $n=4$. Leaving $i$ unchanged can preserve an initial equation forever without producing any answer. The first change breaks the intended postcondition; the second breaks algorithm termination. A trace can reveal these failures, while the two proof obligations explain them.

The exact-arithmetic assumption has a concrete boundary. In a stipulated unsigned eight-bit model where each addition wraps modulo $256$, $n=23$ fits in the input representation, but its intended triangular number is $276$. The stored accumulator instead finishes at $20$, so the mathematical postcondition fails. This is integer overflow, and the proof above does not apply to that altered model. Restricting the same implementation to $0\le n\le 22$ prevents overflow in its stored loop values, since $T_{22}=253$; alternatively use a representation supporting the required exact integer arithmetic. The equations in the proof are mathematical statements, not instructions to evaluate products in eight bits.

The summatory totient function is $\Phi (x)={\sum }_{n\le x}\phi (n)$. It counts the coprime ordered pairs $(a,b)$ with $1\le a\le b\le x$. The identity ${\sum }_{d\mid n}\phi (d)=n$ yields ${\sum }_{j=1}^x\Phi (\lfloor x/j\rfloor )=x(x+1)/2$ for a positive integer $x$.

For an integer $n>1$ with prime factorization $n={\prod }_{j=1}^r{p}_j^{e_j}$, this is the sum of its prime factors with each repeated $e_j$ times. For example, $s(18)=2+3+3=8$. It differs from the sum of distinct prime factors.