Square number Created 2026-09-29 Updated 2026-11-05
A square number is an integer of the form for some integer . Consecutive nonnegative squares differ by .
Square part of an integer 2026-10-20
Square root of an integer Created 2026-10-20 Updated 2026-11-05
For a nonnegative integer , its square root is the unique nonnegative real number whose square is . It is an integer exactly when is a perfect square; otherwise it is an irrational number. Indeed, if with coprime positive integers , then forces every prime divisor of to divide , so .
For example, , whereas is irrational. The integer square root is a different operation: it rounds down, so the integer square root of is .
Square-zero criterion for a two-by-two matrix Created 2026-10-14 Updated 2026-11-05
For a real or complex two-by-two matrix , the Cayley-Hamilton theorem reads . Hence exactly when . Conversely, if for any positive integer , every eigenvalue is zero and the same identity gives . Thus a nonzero nilpotent matrix of this size has nilpotency index two.
Squaring recurrence under integer halving Created 2026-10-25 Updated 2026-10-31
For at and otherwise, put for positive integer . Taking logarithms gives , hence and . These constant-value plateaux have exponential envelopes , but do not justify for all integer inputs.
Sqube Created 2026-10-20 Updated 2026-11-05
A sqube is a positive integer for distinct prime numbers . The ordering matters: , whereas . By unique prime factorization, the exponents identify the ordered pair from the resulting integer.
Every sqube is an Achilles number. It is a powerful number, because both prime exponents are at least two. It is not a perfect power, because the greatest common divisor of the exponents is one. This connects the square-cube construction to two general factorization classes.
Stable record placement in counting sort 2026-10-18
Initialize a mutable endpoint array to the inclusive cumulative counts . Scan input array indices . For each complete sorting record with sort key , first decrement , then write at output array index . This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, final scan paragraph and stability paragraph after Theorem 11.7
In the worked example, the first input sorting record read is at array index six. Its endpoint changes from to , so the complete sorting record goes to . Next, changes from seven to six and goes to . Writing before the decrement at the old endpoint would put outside its reserved integer interval and try to put beyond the output array. All seven writes are:Each endpoint changes only when a sorting record with its own sort key is placed. Consequently, stays at five through the placements of before dropping to four for .
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 outputThe same array
end successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas 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 be the number of already placed sorting records with sort key . A loop invariant isAll integer intervals here mean output array indices. Initially , so each whole reserved integer interval is unfilled. When the next sorting record has sort key , fewer than such occurrences have been placed, giving . Decrementing selects a fresh slot inside its reserved integer interval. At termination, and : 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 . The backward scan visits first and puts it farther right in their shared integer interval. When 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 at positions five, four, three. A forward scan can instead be stable if it starts from and fills each integer interval left to right, incrementing after each write. The scan direction and endpoint convention must agree.
Count initialization takes writes, output initialization takes writes, counting takes updates, the prefix sum pass takes updates, and placement takes writes. Hence time complexity and auxiliary storage are 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]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, auxiliary counter and output arrays, loop-cost discussion and Theorem 11.7
For example, three sorting records with sort keys zero, and zero require one million counters if ; unused sort keys still incur initialization and prefix sum work. The bound is therefore linear in the input length only when . Empty input skips the record scans, but this implementation still initializes counters and accumulates their prefix sums. For nonempty input, counting all 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- 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 (combinatorics) 2026-10-13
Stars and bars counts tuples of nonnegative integers with a prescribed sum. For integers and , its statement isSuch a tuple is a weak composition of an integer. Think of labelled bins: counts identical objects in the first bin, 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]
https://math.mit.edu/~fgotti/docs/Courses/C.%20Combinatorial%20Analysis/6.%20Compositions/Compositions.pdf. Felix Gotti, MIT 18.211, Lecture 6: Compositions, Proposition 1 and Example 3
Computed example. With and , the number of weak compositions of an integer is . The string
••|•|•• encodes : two dots before the first bar, one between the bars, and two after the second. For a fixed first-bin count , the second-bin count can be any integer from to and the third is forced. Thus the direct count is .Stars and bars for five identical objects and three labelled bins: ordinary splits, adjacent bars, and bars at either end
. Details. Adjacent bars encode an empty middle bin:
••||••• gives . A bar at the left end encodes an empty first bin, as in |••|••• for ; a bar at the right end encodes an empty third bin, as in ••|•••| for . These are valid weak compositions of an integer. For every count is zero, and for the unique tuple is , consistent with .Proof outline. Replace each count by that many dots and separate successive groups with bars. Reading the group sizes reverses this construction, so it is a bijection between weak compositions of an integer and strings of dots and bars. Choose the bar positions among 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 for ; for there are none. Subtract one from every count, setting . This is a bijection to weak compositions of an integer of , so stars and bars gives . For five objects and three bins, this is , with the six positive tuplesFor instance, shifts to , whose sum is . Sorting the six positive tuples collapses them to just two integer partitions, and . 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.
Stateful channel iteration and Fibonacci numbers Created 2026-10-25 Updated 2026-10-31
Consider a component that remembers its previous input and maps input to , then sets . Feeding each output back into the same component gives state transition . Starting at , the successive outputs are , the Fibonacci numbers after 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.
Stationary workload of an exponential-payload queue Created 2026-10-14 Updated 2026-11-05
With packet arrival rate lambda, independent exponential payloads of mean one and byte-service rate C, let . The number N of unfinished packets has law . Conditional on N=n, the remaining payloads are n independent unit-mean exponentials, including the in-service residual by memorylessness. Summing their Laplace transforms gives . Thus W has mass at zero and, conditional on positivity, is exponential with rate . The probability of at least r headers is instead for integer r.
Stirling formula Created 2026-09-24 Updated 2026-10-14
Stirling's formula turns the long product defining a factorial into a short expression. For positive integers , putThen as . This is asymptotic equivalence: , 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 . The Gamma function extends this approximation beyond integer inputs. [ref]
https://dlmf.nist.gov/5.11. NIST Digital Library of Mathematical Functions, §5.11: Gamma-function asymptotic expansions
For ,The leading estimate is about low. Multiplying by the first correction factor giveswhich is about low. The Stirling correction by Gaussian moments explains why this factor is 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 objects. Equivalently, for independent fair coin tosses, the binomial distribution assigns probability to exactly heads. An exponentially large count becomes a simple probability scale after cancellation.
For numerical calculations, taking the natural logarithm yieldswhere . Computing a logarithm of a large factorial avoids representing the factorial itself. The Robbins bounds for Stirling's formula give a finite- interval for this logarithmic remainder, rather than only a limiting statement.
The factor 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]
https://commons.wikimedia.org/wiki/File:Methodus_differentialis,_sive_tractatus_de_summatione_et_interpolatione_serierum_infinitarum_(IA_10053880bsb).pdf. James Stirling, Methodus differentialis (1730), digitized original and bibliographic record
Stone theorem for the circle group Created 2026-10-14 Updated 2026-11-05
A strongly continuous unitary representation of the circle group splits as an orthogonal sum of character subspaces. The projections are . Character orthogonality makes them mutually orthogonal, and Fejér sum shows their ranges span the represented Hilbert space. The self-adjoint generator has integer eigenvalues, with domain given by .
Størmer's theorem Created 2026-10-20 Updated 2026-11-05
Størmer's theorem states that for any fixed finite set of primes, there are only finitely many pairs of consecutive positive integers whose prime factors all belong to . Equivalently, the equation has only finitely many solutions in positive -smooth integers.
For , the pairs include and . The underlying method reduces the search to finitely many Pell equations by separating square factors from the products of allowed primes. The allowed prime set must stay fixed; allowing it to grow with the candidate integers would remove the finiteness assertion.
Straightening of a symmetric-group character indexed by a composition Created 2026-09-28 Updated 2026-11-05
For the alternating expression indexed by an integer composition, swapping two adjacent entries of negates . If two entries coincide the expression vanishes; otherwise sorting produces, up to sign, the irreducible character indexed by the resulting partition.
The Hamming number stream merges its shared multiples by two, three and five. To emit its first values, each of the fixed number of mapped streams and merge nodes advances at most positions. With lazy evaluation that shares each evaluated list cell, this takes 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.
Strictly stable distribution Created 2026-10-05 Updated 2026-11-05
A probability distribution is strictly stable with index if for every positive integer , for independent copies. Here no centering term is allowed, unlike in the general definition of a stable distribution.
Strong induction Created 2026-09-24 Updated 2026-10-18
Strong induction establishes a proposition for all integers . Prove ; then, for each , assume every with and prove . The induction hypothesis includes all earlier cases, so the inductive step can use whichever smaller indices it needs. It cannot use itself.[ref]
Mathematics for Computer Science by Eric Lehman and others. §5.2.1, printed p. 125: strong induction principle
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.
Strong induction for factorization existence 2026-10-18
Every integer has a prime factorization. The induction base case is prime. For a larger integer, either it is prime or it is , with . The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for . This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.[ref]
Mathematics for Computer Science by Eric Lehman and others. §5.2.2, printed pp. 125–126: existence of a product of primes; the statement here does not include uniqueness
For the chosen number , one possible recursive decomposition isThe step at needs results for and , rather than a result for . 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 step for 84 can use 6 and 14: the induction hypothesis covers both
. Original factorization tree , followed by and . Arrows show recursive dependencies toward smaller integers, rather than the order of increasing induction. The strip at the bottom marks the earlier cases available at the step for , with the required and highlighted. No use of the unproved case is permitted in the hypothesis. Details.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.
Strong liar 2026-11-05
A strong liar for an odd composite integer is a base for which the Miller-Rabin primality test reports a pass. Write with odd. A base is a strong liar whenThe base “lies” because these conditions hold for every allowed nonzero base when is prime, but can also hold for a composite.
For , base 2 is a strong liar because and divides . For every odd composite, strong liars occupy at most a quarter of the standard base sampling space; independently sampling bases bounds all-pass error by . A fixed handpicked list needs a separate guarantee for the intended input range.[ref]
Probabilistic Algorithm for Testing Primality by Michael O. Rabin. §§1–2, strong-pseudoprime condition and quarter bound
Strongly additive arithmetic function Created 2026-10-06 Updated 2026-11-05
An additive arithmetic function is strongly additive when for every prime number and every positive integer . Its value therefore depends only on the distinct prime factors:The prime omega function is an example: , because both integers have the same prime factors, namely and . By contrast, the total number of prime factors is a completely additive function and counts multiplicity, giving and . When , there are no prime factors, so the empty sum gives .



