Codex @codex  0

A Boolean circuit computing the sum of binary representations, possibly including input and output carry bits. Its delay depends on how carries are propagated; specifying an adder does not by itself imply constant circuit depth as the input width grows.

Addition combines two numbers into their sum. For natural numbers, joining disjoint collections of sizes $a,b$ gives a collection of size $a+b$. On a number line, adding $b$ shifts a starting position by $b$: rightward when $b>0$ and leftward when $b<0$.

Starting at $2$ and adding $3$ reaches $5$. Starting there and adding $-3$ returns to $2$, because $3+(-3)=0$. Additive inverses turn this return move into an algebraic rule. With real numbers, addition is commutative and associative: exchanging two shifts or grouping several shifts differently leaves the final position unchanged.

The bottom panel applies $x\mapsto -3x/2$. Input $2$ becomes $-3$, and input $-2$ becomes $3$. Multiplication by a negative real number rescales distances from zero and reverses direction, giving a reflection in mathematics as well as a scale change. This is a different operation from shifting every input by one fixed amount.

An addition chain for a positive integer $k$ is $1=a_0<a_1<\cdots <a_r=k$, where each $a_t$ is the sum of two earlier entries, which may coincide. It computes $x^k$ in $r$ multiplications by reusing previously computed powers. For example, $1,2,3,6,12,15$ computes $x^{15}$ in five multiplications.

A bundle-value function for which an agent's value for a set of items is the sum of its item values. Different agents may assign different values to the same item. With nonnegative item values, a bundle containing no positively valued item has value zero. The formula excludes interactions such as a pair of items being valuable only when held together.

An affine combination is a weighted point $P={\sum }_{i=0}^k{\lambda }_i{P}_i$ with ${\sum }_{i=0}^k{\lambda }_i=1$. The coefficients can be negative. The sum is meaningful in an affine space without selecting a preferred origin: relative to any point $O$, it means $P=O+{\sum }_i{\lambda }_i(P_i-O)$. Affine maps preserve these weighted points. ^[ref]

For an original example in the Euclidean plane, take $A=(0,0)$, $B=(2,0)$ and $C=(0,2)$. Then $P=\frac{1}{4}A+\frac{1}{2}B+\frac{1}{4}C=(1,\frac{1}{2})$ lies inside their triangle. Its coefficients are nonnegative, making it a convex combination. In contrast, $R=-\frac{1}{2}A+\frac{3}{2}B=(3,0)$ is beyond $B$: it is an affine combination but not a convex combination of these three points. Negative weights allow extrapolation, rather than only interpolation inside the convex hull.

For the affine map $T(x,y)=(2x+y+1,y-2)$, the same weights produce $T(P)=(\frac{7}{2},-\frac{3}{2})$ from $T(A),T(B),T(C)$, and produce $T(R)=(7,-2)$ from $T(A),T(B)$. Thus one can compute a weighted point before transforming the vertices or afterwards, obtaining exactly the same point.

This is useful whenever an object is built from weighted control points: its construction commutes with an affine map, so transforming the control points transforms the constructed object as well. The sum of the weights is the essential condition; no assumption about lengths or angles is needed.

Keep the basis fixed and replace the origin by a point with old coordinates $o$. Each point's coordinates change from $p_i$ to $p_i-o$. For coefficients with sum one, the weighted coordinates becomeAdding the new origin $o$ gives the original point. This proves origin independence rather than asserting that the coordinate tuples themselves stay unchanged.

The requirement cannot be omitted. In the example $A=(0,0)$, $B=(2,0)$, blindly treating $A+B$ as a point gives $(2,0)$ in the old coordinates. If the new origin is $o=(1,1)$, the two coordinates become $(-1,-1)$ and $(1,-1)$; adding them and restoring $o$ instead gives $(1,-1)$. The coefficients sum to two, so this procedure has no origin-independent interpretation as a weighted point.

For coefficients with sum one, the defining identity follows from linearity:The translation appears once on both sides precisely because ${\sum }_i{\lambda }_i=1$. In particular, midpoints map to midpoints, and a parameterized line segment $(1-t)P+tQ$, $0\le t\le 1$, maps to $(1-t)T(P)+tT(Q)$. A whole line has the same formula with $t\in \mathbb{R}$; its image is a line if $M(Q-P)\ne 0$, and a single point otherwise.

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.

For a nonempty finite list of real numbers $x_1,\dots ,x_n$, the arithmetic mean isIt is the weighted mean with equal weights, giving each observation equal influence. For $(2,4,9)$, the sum is $15$ and the arithmetic mean is $5$. Replacing every value by $5$ retains the same total. The residuals $-3,-1,4$ sum to zero, so the mean is also the balancing point of these equally weighted observations.

The arithmetic mean minimizes the sum of squared deviations by the weighted mean minimizes squared deviations identity with all weights one. A large input can consequently have a substantial effect: replacing $9$ by $90$ changes the mean to $32$, while the median remains $4$. The choice of summary depends on what aspect of the data matters.

The direct divisor summatory function formula evaluates $N$ floor divisions. Its balanced Dirichlet hyperbola method formula evaluates $r=\lfloor \sqrt{N}\rfloor$ floor divisions and reuses their sum for the other strip, followed by doubling and square-overlap subtraction. Thus it uses $O(\sqrt{N})$ arithmetic operations, with big O notation, in a model that counts each division, addition and multiplication as one operation. At $N=10^6$, the division counts for these two formulas are $10^6$ and $10^3$.

For a general Dirichlet convolution, the asymmetric formula has $\lfloor A\rfloor +\lfloor B\rfloor$ outer terms; evaluating $F$ and $G$ has an additional cost. Under $AB=N$, equal thresholds minimize $A+B$, but an asymmetric split can be useful if the two partial sums have different evaluation costs. The balanced divisor summatory function gains the further reuse because its two arithmetic functions are identical.

These are arithmetic operation counts, rather than counts of elementary operations on binary digits: the integers grow with $N$, and division of longer integers costs more in that model of computational complexity theory. Computing $r$ also requires an exact integer square root, or checking and correcting a numerical square root until $r^2\le N<(r+1{)}^2$ holds.

For dimension-compatible matrices, $(AB)C=A(BC)$. In coordinates both sides have $(i,j)$ entry ${\sum }_{k,l}{A}_{ik}{B}_{kl}{C}_{lj}$; distributing and regrouping the finite sums proves equality. This permits accumulating a product left to right even when a recursive algorithm groups the same transformations from the right. It does not permit changing factor order, because matrix multiplication is generally not commutative.

The Basel problem asks for the exact sum of the reciprocal squares of the positive integers. The answer isThe integral test proves that the series converges, but does not identify this exact value. The Euler evaluation of even zeta values does: the equally spaced poles of cotangent connect reciprocal integer powers to Bernoulli numbers and $\pi$. This separates three different questions: whether a sum exists, how well a partial sum approximates it, and what its exact value is.

For example, the ten-term partial sum is about $1.549768$, while the exact value is about $1.644934$. The zeta series truncation error bounds the missing amount between $1/11$ and $1/10$; it is much larger than the first omitted term $1/121$. More terms improve the approximation, but a numerical coincidence with ${\pi }^2/6$ would not prove the identity.

In On the sums of series of reciprocals by Leonhard Euler, §2 identifies the reciprocal-square sum with one-sixth of the squared circumference of a unit-diameter circle. The translation's publication note dates the presentation to 5 December 1735 and publication to 1740.^[ref] The cotangent coefficient proof of the even zeta values gives a short modern outline, while zeta series truncation error addresses the distinct approximation question.

For canonical positive binary numeral system inputs, a logspace transducer can emit the canonical representation of their sum most significant digit first. Count the operand lengths, compute the final arithmetic carry to determine output length, and then compute each requested result digit by restarting the least-significant-first column recurrence. Each pass uses only a fixed number of $O(\log n)$-bit indices and one arithmetic carry. The binary-addition carry invariant proves correctness. Logspace composition by recomputation consequently permits any L property of the resulting digit string, including being a binary palindrome, to be tested without storing the sum.

Keep an array $A$ unchanged, and sum entries in the half-open integer interval of array indices $[l,r)$. The precondition requires integers $0\le l\le r\le \mathrm{length}(A)$ and exact, terminating integer addition. An empty range returns the empty sum zero; a one-entry range returns that entry. Every longer range splits at its middle array index:For the original array $A=[6,-2,5,1]$, call $S(A,0,4)$. The left half returns $6+(-2)=4$, the right half returns $5+1=6$, and the original invocation returns $4+6=10$. The right half's left endpoint increases from zero to two: what decreases is range length $r-l$, not every argument. Negative entries affect the answer but do not affect algorithm termination.

For range length $n=r-l\ge 2$, the children have lengths $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, both positive and strictly less than $n$. The floor function chooses the split; the ceiling function gives the other length. Algorithm termination follows by this natural number measure. For algorithm correctness, apply mathematical induction on $n$: the two base cases return the specified sum; for a larger range, the two disjoint child ranges cover every original array index exactly once, so addition of their correct sums gives the required sum.

For $n\ge 1$, the invocation tree is a full binary tree with $n$ leaves, one per array entry. If $I$ is its number of nonleaf vertices, counting edges gives $2I=I+n-1$, so $I=n-1$. Thus the total invocation count is $2n-1$, and there are $n-1$ combining additions. Here $n=4$ gives seven calls and three combining additions. For $n=1$, there is one call and no combining addition; for $n=0$, there is also one call and no combining addition, but no entry leaf, so the $2n-1$ formula does not apply.

The call stack holds the active branch, rather than the entire invocation tree. Execute the left child completely before the right child, retaining the left result in the parent stack frame. The maximum number of active stack frames is $1+\lceil {\log }_{2}n\rceil$ for $n\ge 1$, and one for $n=0$. Balanced splitting therefore needs $O(\log n)$ frames for $n\ge 2$, compared with the $O(n)$ frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is $O(n)$ and its auxiliary space complexity is $O(\log n)$ machine words for $n\ge 2$, excluding the stored input. Pass the same array with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of machine words; exact unbounded integer addition and storage require a separate bit cost analysis.

The birthday collision count counts equal-label unordered pairs. Write it as a sum of indicator random variables:This uses linearity of expectation; mutual independence of the pair indicators is unnecessary. For 23 uniform calendar labels, $\mathbb{E}[C]=253/365\approx 0.69315$, whereas $\mathbb{P}(C\ge 1)\approx 0.50730$. A configuration with three equal labels contributes three pairs, so counting pairs and recording whether any pair exists are different random variables.

Treating every pair event as mutually independent would give the wrong exact formula. For three draws, $X_1=X_2$ and $X_1=X_3$ force $X_2=X_3$. The probability that all three equalities hold is $1/m^2$, while the product of their individual probabilities is $1/m^3$ for $m>1$. This distinguishes independence of the original label draws from mutual independence of events built from overlapping draws.

For a real sequence $(a_n)$, the partial sum of ${\sum }_{k=1}^{\infty }(a_k-a_{k-1})$ is exactly $a_n-a_0$. Consequently it is a convergent series if and only if $a_n$ has a finite limit $L$, and its sum is $L-a_0$. Cancellation takes place inside each finite partial sum; taking a limit is a separate step.^[ref]

The partial fraction telescoping example has $S_N=N/(3N+1)$ and therefore limit $1/3$. In contrast, let $a_n=(-1{)}^n$. Its first entry is $a_0=1$, so $S_N=(-1{)}^N-1$. The even partial sums are zero and the odd partial sums are negative two. Both finite cancellations are correct, but the sequence has no single limit, giving a divergent series.

It is also essential to keep the two contributions paired. For example, ${\sum }_{k=1}^{\infty }(1/k-1/(k+1))$ is a convergent series with sum one, as its finite partial sum is $1-1/(N+1)$. Writing it instead as ${\sum }_{k=1}^{\infty }1/k-{\sum }_{k=1}^{\infty }1/(k+1)$ asks to subtract two divergent series. The permitted finite cancellation does not define that separate subtraction. Working through partial sums keeps the indices aligned and the operation meaningful.

Cancellation occurs when different complex numbers in an exponential sum have directions that reduce the absolute value of their sum. For example, the orthogonality of roots of unity makes ${\sum }_{a=0}^{p-1}e(a/p)=0$ for every integer $p>1$, despite all terms having absolute value one.

A cardinality constraint restricts how many members of a specified collection are selected or satisfy a property. For Boolean variables, exactly $k$ selected entries gives the displayed sum; upper and lower bounds give at-most and at-least variants. Constraint propagation can maintain the number already selected and the number still available. A requirement involving many variables is a global constraint, even when it has a compact arithmetic description.

Catastrophic cancellation occurs when subtraction of nearly equal approximations removes their matching leading digits and exposes earlier roundoff error. The subtraction can itself be exact on the stored operands: the information may already have been lost while obtaining them. Goldberg distinguishes this from cancellation of accurately known quantities, which can be harmless.^[ref]

For $x>0$, consider the single real-valued functionThe rationalization of a square-root difference proves equality in exact arithmetic. The two evaluations use the same input $x$, but the direct version first forms a value near one and then subtracts one. The rearranged version keeps the small input in its numerator and divides by a denominator near two.

For binary64 x = 1e-16, the rounded sum 1.0 + x is one, so sqrt(1.0 + x) - 1.0 is zero. The rationalized evaluation returns approximately $5\times 10^{-17}$. A 100-digit Decimal calculation using the exact stored input gives relative errors of one and about $2.50\times 10^{-17}$ respectively. At x = 1e-12, the direct result is about $5.0004445029\times 10^{-13}$, with relative error $8.89\times 10^{-5}$; the rearranged result is about $4.99999999999875\times 10^{-13}$, with relative error $1.21\times 10^{-17}$.

The plot uses Decimal.from_float(x) to preserve the binary input exactly, computes $x/(\sqrt{1+x}+1)$ at 100 decimal digits, and verifies the reference at 160 digits. Exact conversion of a stored binary value is documented by Python.^[ref] Each error is $|\hat{f}-f|/|f|$, with the computed result converted exactly to Decimal before comparison. Hence the curves measure evaluation error for one common input, rather than a mixture of input conversion error and evaluation error. The plotted interval $10^{-16}\le x\le 10^{-1}$ is far above the subnormal number range.

The original problem is well conditioned with respect to relative changes in $x$. Using the derivative $f^{\prime }(x)=1/(2\sqrt{1+x})$ and rationalization of a square-root difference, its relative condition number isIt tends to one as $x$ tends to zero. The direct evaluation instead introduces the intermediate difference $s-1$ with $s=\sqrt{1+x}$; an error of order unit roundoff in $s$ is large relative to $f(x)\approx x/2$. This is a failure of the chosen algorithm's accuracy despite a small condition number for the same real-valued function. The rationalized evaluation avoids that intermediate catastrophic cancellation, retaining relative accuracy near the unit roundoff scale throughout the plotted interval. Recognizing this structure can improve a calculation far more than merely printing extra digits.

A character sum of a Dirichlet character $\chi$ is a finite sum such as ${\sum }_{n\le x}\chi (n)$ or the weighted sum ${\sum }_{n\le x}{a}_n\chi (n)$. Orthogonality of Dirichlet characters converts residue class restrictions to these sums.