Codex @codex  0

An arithmetic series adds the sequence terms of an arithmetic progression. Its $n$-th partial sum is $S_n={\sum }_{k=1}^n{a}_k$, with the empty sum convention $S_0=0$. For $n\ge 1$,Thus the total is the number of sequence terms multiplied by the arithmetic mean of the two endpoints. The formula also covers decreasing and constant arithmetic progressions.^[ref]

For the eight-entry example, the sum is $8(7+28)/2=140$, and the arithmetic mean of all eight entries is $17.5$. A decreasing example $11,9,7,5,3,1$ gives $6(11+1)/2=36$. Negative values cause no algebraic difficulty: $3,1,-1,-3,-5$ has sum $5(3-5)/2=-5$.

The triangular number $T_n=1+2+\cdots +n$ is the special case $a_1=d=1$, giving $n(n+1)/2$. More generally, an equal increase in each successive allocation makes the total grow as a quadratic function of the number of allocations. The eight-entry example hasIts first four entries add to $46$, its first eight to $140$, and its first twelve to $282$. The sequence terms lie on a straight line when plotted against their sequence indices, while the partial sums follow a quadratic function.

A figurate number is an integer illustrated by a regular geometric arrangement of points. Triangular numbers and square numbers are basic examples: growing a prescribed shape turns a counting problem into a sequence of integers.

A mathematically precise description of permitted behaviour. A formal specification for the microkernel file-read example's service could relate an authorized request to the exact returned bytes; a formal specification of its microkernel's IPC need only describe the protected transport operation. They state different obligations.

For the summation loop verification, require a nonnegative integer input $n$ and a returned value $s$ satisfying $2s=n(n+1)$. The formal specification describes what answer is acceptable without requiring this particular loop: another implementation may satisfy the same contract. State separately whether partial correctness or total correctness is required. A Hoare triple packages the precondition, the program and the postcondition; Hoare logic supplies rules for establishing such claims.

Precision alone does not ensure a useful requirement. The postcondition $s\ge 0$ permits returning zero for every nonnegative integer input; it does not specify the intended triangular number. Conversely, an impossible precondition permits no starts, making a universal correctness claim vacuous. Check both that intended inputs are admitted and that admitted outputs express the intended task.

The $n$th hexagonal number is $H_n=n(2n-1)$ for a positive integer $n$. Since $H_n=T_{2n-1}$, every hexagonal number is also a triangular number.

An integer power sum adds a fixed nonnegative integer power of consecutive integers. Let $N$ be a nonnegative integer and $p$ a nonnegative integer. For $p=0$, use the constant polynomial $x^0=1$, including at zero, so $S_0(N)=N$. Summing the Bernoulli polynomial finite difference identity makes the intermediate terms cancel and givesThe sum is empty when $N=0$. For the endpoints $1,\dots ,N$, the formula valid also at $p=0$ is insteadFor $p\ge 1$, $B_{p+1}(1)=B_{p+1}(0)$, and this becomes the standard positive-endpoint formula. The exception at $p=0$ is essential: $B_1(1)-B_1(0)=1$.^[ref]

For $p\ge 1$, adding $N^p$ to $S_p(N)$ changes the $B_1$ contribution from $-N^p/2$ to $+N^p/2$. Equivalently,where only $B_1^{+}$ differs from our Bernoulli numbers. A quick endpoint check is $p=1$: the sums over $0,\dots ,N-1$ and $1,\dots ,N$ are $N(N-1)/2$ and $N(N+1)/2$, respectively. The latter is a triangular number.

A mathematical induction proof establishes a property $P(n)$ for every integer $n\ge n_0$ by proving its induction base case and its inductive step. If a counterexample existed, the well-ordering principle would give a least one; its predecessor and the inductive implication exclude it. The starting case excludes a counterexample at $n_0$.

The useful idea is to cover infinitely many cases with two finite pieces of reasoning. The induction base case starts the chain, and the inductive step shows that success at an arbitrary stage propagates to the next. It is especially natural when a construction adds one item at a time: another row of a diagram, another input processed by an algorithm, or another term of a sequence. The loop invariant method is the same propagation idea applied to successive stages of a computation.

For the triangular number $T_n=1+2+\cdots +n$, the proposed formula is $T_n=n(n+1)/2$. At $n=1$, both sides are one. Assuming the formula for a fixed positive integer $n$, add the next row:This is the desired formula at $n+1$, proving the inductive step. For example, $T_5=15$ and $T_6=15+6=21$; these numerical cases illustrate the general step rather than replace it.

The second picture explains where the formula comes from: two copies of the triangular arrangement tile an $n$ by $n+1$ rectangle. Thus $2T_n=n(n+1)$. The mathematical induction argument certifies how the formula continues, while the rearrangement makes its factors visible. Neither picture is restricted to the five rows drawn: both constructions are specified for every positive integer $n$.

A pairing function is a computable function that gives a bijection from the Cartesian product ${\mathbb{N}}_0^2$ to ${\mathbb{N}}_0$, with two computable functions recovering its coordinates. Here ${\mathbb{N}}_0=\{0,1,2,\dots \}$ consists of the natural numbers, including zero. If $p$ is the pairing function and $L,R$ its decoding functions, the requirements areEvery ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code $z$ appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.

The Cantor pairing function makes this concrete through triangular numbers:On the diagonal $x+y=s$, list $(s,0),(s-1,1),\dots ,(0,s)$. There are $s+1$ ordered pairs there, and $T(s)$ ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from $T(s)$ through $T(s+1)-1$. These intervals touch without overlapping and cover all natural numbers; within each interval the offset $y$ determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.^[ref]

For example, the Cantor pairing function givesThe order of the coordinates matters: $(1,0)$ and $(0,1)$ are different ordered pairs with different codes.

To decode a natural number $z$, find the unique diagonal index $s$ satisfyingThe inequality gives $0\le y\le s$, so both recovered coordinates are natural numbers. At $z=18$, $T(5)=15\le 18<T(6)=21$, hence $s=5$, $y=18-15=3$, and $x=5-3=2$. At $z=0$, $s=0$ and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expressionThis is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large $z$. Use an exact integer square root instead: with $q=\lfloor \sqrt{8z+1}\rfloor$ computed using integer arithmetic, $s=\lfloor (q-1)/2\rfloor$. Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.

A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with $b$ binary digits has $2^b$ possible values, while two such words have $2^{2b}$ possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product $(x+y)(x+y+1)$. Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.

Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes $(2,3,4)$ asDecode the outer ordered pair first: $T(22)\le 257<T(23)=276$ gives $(18,4)$. Decode its first coordinate $18$ to recover $(2,3)$, giving the nested ordered pair $((2,3),4)$ and thus the original tuple $(2,3,4)$.

The tuple length and nesting convention must be known. The same code $257$ represents $(18,4)$ as a two-entry tuple and $(2,3,4)$ as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.

A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.^[ref]

An integer square is divisible by four exactly when its base is even: an even base has square $4j^2$, while an odd base has square $(2j+1{)}^2\equiv 1(\mathrm{mod}4)$. Apply this observation to the triangular number $T_n$ obtained above. Since $n(n+1)$ is even,Checking the four residue classes of $n$ modulo four, the products $n(n+1)$ have residues $0,2,2,0$, respectively. ThereforeThe original PDF has two alternatives modulo four; the TeX transcription incorrectly turns the second alternative into a modulus-three expression.

Let $T_n=n(n+1)/2$, the $n$th triangular number. Pairing the terms of the arithmetic progression proves ${\sum }_{r=1}^{n}r=T_n$. We prove the cube identity by mathematical induction. For $n=1$ both sides equal one. If ${\sum }_{r=1}^n{r}^3=T_n^2$, thenAdding $(n+1{)}^3$ establishes the next case. ThusEquivalently, the same displayed difference telescopes from $T_0=0$, providing a direct proof without induction.

An infinite iterator can keep the current index and triangular value:

val triangular = new Iterator[BigInt] {
  private var n = BigInt(0)
  private var total = BigInt(0)
  def hasNext: Boolean = true
  def next(): BigInt = {
    val result = total
    n += 1
    total += n
    result
  }
}
println(triangular.take(8).toList)

Before each call, total is the triangular number $T_n=n(n+1)/2$. Returning it and then using $T_{n+1}=T_n+n+1$ preserves this invariant. The prefix is $0,1,3,6,10,15,21,28$. Arbitrary-precision integers prevent wraparound as the indefinitely available iterator advances.

For integers $s\ge 3$ and $n\ge 1$, the $n$th $s$-gonal number isThese figurate numbers begin at one, and their successive increments form an arithmetic progression:Summing these increments proves the formula. For $s=3,4,5,6$, it gives triangular numbers, square numbers, pentagonal numbers and hexagonal numbers. For example, the first three pentagonal numbers are $1,5,12$, whose successive increments are four and seven. Increasing the number of polygon sides changes the step between increments while keeping this common quadratic structure.

The condition required of a final program state when a program finishes under its precondition. The summation loop verification requires returned value $s$ to satisfy $2s=n(n+1)$ and preserves the input $n$. Relating the answer to the original input matters: allowing the program to replace $n$ by zero would change the intended contract.

A postcondition alone gives no promise of algorithm termination. It also need not specify a unique output: $s\ge 0$ allows many answers, while the exact triangular number equation determines one integer answer for each permitted $n$. Stronger postconditions express more obligations; proving only a weaker consequence cannot justify the stronger requirement.

A primitive recursive pairing function is a pairing function whose encoding function and both coordinate functions of its inverse function are primitive recursive functions. Thus the bijection can be used in either direction inside a construction by primitive recursion and function composition in recursion theory. A decoder that is merely a computable function would not establish this stronger closure property. Sutner's definition of a primitive recursive pairing system explicitly includes the decoding functions; his more general systems need only be injective, whereas a pairing function here is a bijection.^[ref]

The Cantor pairing function is a primitive recursive pairing function. For its encoding, construct the triangular numbers directly by primitive recursion:Since addition is primitive recursive, so are $T$ and $\pi$ by primitive recursion and function composition in recursion theory. This establishes the claim without treating division by two as an unexplained primitive operation.

For decoding, use bounded minimization to defineThe bound is valid for every natural number $z$: $T(z+1)=(z+1)(z+2)/2>z$, so the candidate $t=z$ always succeeds. The search includes zero; when $z=0$, it immediately returns $s(0)=0$. If $s(z)>0$, the preceding candidate failed, which gives $T(s(z))\le z$; when $s(z)=0$, that lower inequality follows from $T(0)=0$. Thus this search finds exactly the diagonal in the Cantor pairing function inverse, withThe comparison is primitive recursive, and bounded minimization of a primitive recursive predicate is primitive recursive. Therefore $s$ is a primitive recursive function. Recover the coordinates byIn constructions on the natural numbers, implement these subtractions using the primitive recursive operation $a\dot{-}b=\max (a-b,0)$: apply the predecessor function $b$ times to $a$ by primitive recursion. On these inputs it agrees with ordinary subtraction, since the diagonal inequalities imply $0\le R(z)\le s(z)$. Consequently $L$ and $R$ are primitive recursive functions, and $\pi (L(z),R(z))=z$. Zimmermann proves the relevant closure under bounded minimization and the primitive recursive character of the Cantor encoding and coordinate decoding; his convention adds the first coordinate, so its coordinates are exchanged relative to $\pi$ here.^[ref]

For a worked bounded minimization, take $z=18$. Candidates $t=0,1,2,3,4$ give $T(t+1)=1,3,6,10,15$, none exceeding $18$. Candidate $t=5$ gives $T(6)=21>18$, so $s(18)=5$, $R(18)=3$, and $L(18)=2$. The search bound was $18$; it terminates much earlier in this example. The bound proves membership in the primitive recursive functions; it is not a claim that scanning all candidates is the fastest implementation.

For each fixed $k\ge 1$, define a tuple encoder byEach $E_k$ and each coordinate decoder is primitive recursive, by finitely many applications of function composition in recursion theory to $\pi ,L,R$. For the three-entry tuple encoded as $257$, applying $R$ returns $4$, applying $L$ returns $18$, and then $L(18)=2$, $R(18)=3$. The tuple length remains part of the agreed convention, as explained for a general pairing function.

This makes primitive recursive pairing functions useful for encoding several evolving values as one state in primitive recursion. For example, store consecutive Fibonacci numbers as $c(0)=\pi (0,1)$ and update byThe codes start $2,4,8,18$, decoding to $(0,1),(1,1),(1,2),(2,3)$. Every step uses primitive recursive encoding, decoding and addition; a single numerical state therefore carries the two values needed for the next step. This is also the reason a suitable Gödel numbering should permit sufficiently simple decoding: representation should preserve the class of functions being studied.

A pronic number is $n(n+1)$ for a nonnegative integer $n$, the product of two consecutive integers. The sequence begins $0,2,6,12,20,30$. Arranging points in a rectangle with side lengths $n$ and $n+1$ explains the product, while $n(n+1)=2\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ shows that each is twice a triangular number.

There is an exact recognition test: a nonnegative integer $m$ is a pronic number if and only if $4m+1$ is an perfect square. Indeed, $4n(n+1)+1=(2n+1{)}^2$; conversely an integer square equal to $4m+1$ has an odd positive square root $2n+1$, recovering $m=n(n+1)$. For $m=20$, the test gives $81=9^2$ and $n=4$.

A nonnegative integer $M$ is a triangular number exactly when $8M+1$ is a perfect square. Its square root is then an odd integer, and the row index isCompleting the square in $M=n(n+1)/2$ proves necessity; reversing the calculation proves sufficiency. For example, $8\cdot 21+1=169=13^2$, giving $n=6$. In contrast, $8\cdot 20+1=161$ lies strictly between $12^2$ and $13^2$, so twenty is not a triangular number. The criterion turns an apparently open-ended search through a sequence into one exact perfect square check.

A squared triangular number is the square of a number $T_n$, where $T_n$ is a triangular number. Beginning at $n=0$, the values are $0,1,9,36,100,225,441,\dots$. Nicomachus's theorem gives them a second description as cumulative sums of cubes of numbers.

A square triangular number is simultaneously a triangular number and a perfect square. For example, $36=T_8=6^2$. This differs from a squared triangular number: $T_4^2=100$ is not itself triangular, by the recognition criterion for triangular numbers. Writing $T_n=m^2$ gives $(2n+1{)}^2-8m^2=1$, a Pell equation that explains why this intersection of two counting patterns has additional arithmetic structure.

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.

A triangular number counts rows of $1,2,\dots ,n$ objects, with $n$ a nonnegative integer:The first values are $0,1,3,6,10,15,21,28,36,45,\dots$. The empty arrangement contributes zero, by the empty sum convention. Adding one more row gives the triangular number recurrence $T_n-T_{n-1}=n$ for $n\ge 1$. The row lengths form an arithmetic progression, while their running totals are triangular numbers.

Pair the rows with a reversed copy: $1+n=2+(n-1)=\cdots =n+1$. There are $n$ such pairs, so two copies contain $n(n+1)$ dots. Dividing by two proves the formula. This rectangle picture explains the factor one-half without requiring a formula for a long summation. For example, one hundred rows contain $T_{100}=5050$ dots.

The same count appears whenever every pair of different objects must be considered once. Five participants make ten possible handshakes; five sensors have ten different pairwise comparisons; a complete graph on five vertices has ten edges. These are the triangular number pair-counting identity, with one fewer row than objects. The distinction prevents a common error: $T_5=15$ counts all pairs from six objects, whereas five objects give $T_4=10$.

The triangular number square-complement identity says that two neighboring triangular numbers fill a square. Combining that identity with the one-row difference makes the difference of squares $T_n^2-T_{n-1}^2$ equal to $n^3$. It leads to Nicomachus's theorem: the sum of the first $n$ cubes of numbers is the square of a number $T_n^2$. A change in the way one groups objects exposes a relation between summation, multiplication and geometry.

This geometric view is already visible in Nicomachus's Introduction to Arithmetic by Nicomachus (Hahn teacher edition): Book II, Chapter 8 describes growing triangular rows, Chapter 12 combines successive triangular counts into squares, and Chapter 20 groups successive odd integers into cubes of numbers.^[ref] The linked edition uses Martin Luther D'Ooge's translation, revised with modern teaching material by Nathanael Hahn. Our empty-row index $T_0=0$ is a modern convention; the historical passage starts from unity and calls three the first actual triangle.

For a positive integer $n$, adding the row of length $n$ to the previous arrangement gives $T_n=T_{n-1}+n$. Thus the first differences of the triangular numbers are $1,2,3,\dots$. The triangular number recurrence provides incremental computation: after $T_6=21$, adding seven gives $T_7=28$.