The floor function and ceiling function turn a real number into directed integer bounds. They answer two different questions: which integer is the largest one that does not exceed , and which is the smallest one that is not less than ?
Both outputs are integers. These are exact mathematical operations; they need not choose the closest integer, and they do not refer to roundoff error in floating-point arithmetic.
For example,
The fractional part is . The negative example matters: discarding the digits after the decimal point would give , which is truncation toward zero, rather than the floor function's value . At an integer, the floor function and ceiling function agree and the fractional part vanishes.
Figure 1.
Floor and ceiling give enclosing integers; fractional part repeats on each unit interval
. Details.
The usefulness is a bridge from continuous quantities to discrete decisions. An integer count in a closed interval uses both bounds. A ceiling count for fixed-size batches counts how many containers or pages are needed; a floor function counts how many complete groups fit. In Euclidean division, the same bounds specify the quotient, while the fractional part records the scaled remainder. A small amount of notation removes many cases that would otherwise have to be stated separately.
The reflection identity
follows by reflecting the ordered integers across zero: the largest one below becomes the smallest one above . For every integer , translation gives and . These formulas turn upper bounds into lower bounds and move examples between neighboring intervals.
For a historical example of the notation in use, Kenneth E. Iverson's 1962 conference paper A Programming Language lists the floor function, ceiling function and residue operation alongside the ordinary arithmetic operations. It states the two defining inequalities above, then extends operations component by component to vectors and matrices. This shows their role as tools for describing algorithms, rather than merely conventions for writing decimal numbers. [ref]
Floor function Created 2026-09-24 Updated 2026-10-20
The floor is the greatest integer not exceeding the real number . Equivalently, exactly when , for an integer . The floor function is constant on each such half-open interval and has a discontinuity of a function at each integer.
For nonnegative integers and positive integers , is the number of complete groups of size that fit into items. With and , five complete groups use 100 items. Euclidean division writes , retaining the two-item remainder rather than treating the quotient as a number of complete groups.
Floor-half generating function Created 2026-09-24 Updated 2026-11-05
The ordinary generating function of the sequence is
The floor function takes the same value at and . Grouping those adjacent terms gives
which simplifies to the displayed expression. The middle identity follows by differentiating the geometric series. The calculation is valid as an identity of formal power series, or analytically for .
Expanding begins , making the paired values of the sequence visible in the coefficients.
Floor sum 2026-10-20
A floor sum adds values of a floor function, often in the form for integers , , , and . If , it counts lattice points with and . Splitting and into quotients and remainders isolates an arithmetic progression and a constant contribution; swapping the remaining counting axes leads to an Euclidean algorithm reduction.
Franck-Hertz repeated-loss collection model Created 2026-10-18 Updated 2026-10-20
Define a signed offset so that the accelerating region adds kinetic energy . This convention concerns this gap; collector contact fields belong in the effective . An electron emitted with initial kinetic energy and undergoing identical excitation losses reaches the grid with
Each loss excites a fresh chemical atom initially in its ground state. These are repeated payments of the same excitation cost. The index counts events along an electron trajectory, not the ordinal number of an atomic excited state. The outgoing energy also does not locate the last collision: after an early collision an electron can regain enough kinetic energy to cross the barrier.
At fixed , let be the normalized initial-energy probability density function within the ensemble of electrons reaching the grid, and the conditional probabilities for losses within that ensemble. Then the ideal collection law is
Take and exclude paths with insufficient kinetic energy for a loss at its actual collision position. The weights contain collision positions and rates, mean free paths and angular acceptance. This equation is a bookkeeping model, not a derivation of those weights. Multiplying all incident particles by one constant transmission is an additional approximation; real transmission and can vary with .
One analytical extreme assumes , one-dimensional motion and an immediate loss whenever the kinetic energy reaches . With , and , the number of losses and remaining kinetic energy are
Here is the floor function. Collection switches off for an interval of width after each reset, then recovers; the pattern repeats every . For , and , an applied gives , and rejection, whereas gives , and collection. With the dips disappear in this idealization. With no collisions, there is only a single collection onset. Both limits expose the separate roles of loss and filtering.
To draw a smooth illustrative curve, extend this periodic rule mathematically to all and convolve it with a chosen normal distribution of voltage jitter, of standard deviation :
Here is the standard normal cumulative distribution function. Each summand is the smoothed indicator of the accepted interval . The result satisfies and has period . For the figure choose and plot only well beyond the startup region. This is a chosen phenomenological curve, not a Boltzmann equation transport prediction or a fit to measured electric current. Its symmetric troughs center on , rather than the reset voltages . Finite excitation rates, several loss channels, space charge, initial angular and energy spreads, and real electrode geometry can change the trough shape and phase; a single convolution does not solve these effects.
Figure 1.
Illustrative repeated-loss collection and an independent synthetic spacing fit
. Left: the chosen Gaussian-smoothed threshold model, with , , and . Right: separately chosen synthetic trough positions, their ordinary least squares fit and residuals. The points are not extracted from the left curve or a historical trace. Source. Details.
Integer arithmetic 2026-10-13
Integer arithmetic computes with integers. Addition, subtraction and multiplication preserve integer values; division can instead return a quotient and remainder through Euclidean division. For example, gives five complete groups and a remainder of two. The ceiling count for fixed-size batches requires six groups to hold all 102 items.
Mathematical integers have no fixed size bound. A computer representation may have one, so an exact arithmetic formula still requires sufficient space for its inputs and intermediate values. The floor function and ceiling function define mathematical bounds independently of a chosen representation.
For real numbers , the integers in the closed interval begin at and end at , if there are any. Their number is therefore
The extra one includes both ends of the resulting integer interval. The maximum with zero handles an empty intersection: contains no integer, even though it has positive length.
For , the ceiling function selects and the floor function selects , giving . The four points are . For , the count is five, not four: the real length and the number of integer points are different quantities.
The endpoint convention matters. For the half-open interval with , the last allowed integer is , so the count becomes . This handles an integer endpoint without including it accidentally. For example, has four integer points.
Integer logarithm 2026-10-31
For integers and , the integer logarithm is the largest nonnegative integer such that . Equivalently,
The equivalence follows from the monotonicity of exponentiation in its exponent and the definition of the floor function. For example, , so the base-three integer logarithm of is .
A multiplication loop maintains and accepts another factor while . Repeated squaring makes the search faster: precompute starting at , and consider these factors in decreasing . Include a factor when the accumulated product remains at most . If , the loop invariant before considering is . Accepting exactly when halves that uncertainty, proving the greedy algorithm returns . This takes arithmetic operations; it is not the same claim as this bound on bit complexity.
For positive operands in bounded integer arithmetic, test before multiplying by . Integer division makes this equivalent to while preventing integer overflow in a rejected candidate.
For positive integers , the floor function condition is equivalent to the displayed integer inequalities. Since , a witness satisfies . Finding the least with and checking the strict upper bound therefore decides membership by binary search. Scanning successive values with a persistent increasing witness index instead enumerates all values below a bound in linear time arithmetic-operation count. Exact integer comparison avoids floating-point errors near an integer boundary.
Integer-valued function Created 2026-10-20 Updated 2026-11-05
An integer-valued function is a function whose values all lie in , even if its input domain is not discrete. For example, the floor function maps to , while the prime-counting function assigns an integer to every real bound.
A polynomial can be integer-valued on integers without having integer coefficients: takes integer values for every . Its behavior is specified by both its formula and its input domain. On a connected topological SPACE, a continuous integer-valued function is constant, because distinct integer values are separated by open gaps.
Fix an integer base . Let have at most digits in positional notation, treating zero as one digit. For , set using the ceiling function, and . Euclidean division gives
where and . The floor function selects the high block; the remainder selects the low block. Both operands must use the same , including when their actual digit lengths differ.
For odd , the low block has digit positions and the high block has . Leading zero padding aligns a shorter operand without changing its integer value. Padding to a power-of-two length is optional: the split itself works for every . If power-of-two padding is used, the padded length is less than twice the original length, so it changes only a constant factor in the asymptotic analysis.
Every nonnegative integer is a sum of squares with four terms, with zero terms allowed. Precisely, for every integer , there exist nonnegative integers such that
Allowing arbitrary integer roots gives the same statement: changing a root to its absolute value leaves the resulting square number unchanged. Four is a uniform upper bound on the number of nonzero terms, rather than a demand for four positive terms. Repeated square numbers are allowed. Conrad states the positive case and explicitly explains the role of zero terms; follows by taking all four roots zero. [ref]
The small cases make the convention visible:
In particular, could not be a sum of squares with four strictly positive roots, since each term would be at least one. Geometrically, a square of integer side length has area : the theorem says that any nonnegative whole-number total area can be split into at most four such square areas. It does not assert that those squares tile one larger square or a prescribed rectangle.
Figure 1.
Four-square representations as areas counted in unit cells
. The roots for were found by enumerating nonnegative four-tuples. Each panel has the same unit length, and each little cell has area one. The four separate squares illustrate addition of areas, with no claim about tiling a prescribed shape. These are exact arithmetic examples, not measured data. Details.
Why does the fourth term matter? Two square numbers do not suffice for : in modular arithmetic, a square number has remainder zero or one modulo four, so their sum cannot be three modulo four. The sum of two squares theorem gives a complete criterion for the positive integers representable with two terms. Even three terms leave gaps. A square number has remainder or modulo eight; adding three of these, with repetition allowed, never gives seven modulo eight. Thus cannot be sums of three square numbers, although Lagrange's four-square theorem represents all of them with four. This also proves that the bound four cannot be reduced to three.
The modulo-eight obstruction is not the only way that three terms can fail. For example, needs four: if three square numbers added to , their remainders modulo four would force all three roots even. Dividing by four would then express as a sum of three square numbers, contradicting the preceding calculation. These short checks explain the examples without requiring a full classification of sums of three square numbers.
Figure 2.
Minimum number of nonzero square terms for integers from one to one hundred
. Each cell is labelled by the positive integer being represented; its colour records the least number of nonzero square numbers whose sum equals it. Direct enumeration gives requiring one term, two, three, and four. Zero is omitted from the grid and requires no nonzero terms. Zero padding converts every representation into four slots. This finite computation illustrates Lagrange's four-square theorem; it does not prove its assertion for all nonnegative integers. Details.
The practical benefit of Lagrange's four-square theorem is an existence guarantee for a family of Diophantine equations: for every nonnegative integer , the displayed equation has an integer solution. It does not specify a unique solution. For instance, . To find a representation by a finite search, enumerate and test the sum. The floor function supplies a finite bound because no single term can exceed , and sorting roots removes duplicate orderings without discarding any possible sum. The theorem guarantees that the search succeeds.
A greedy algorithm that repeatedly subtracts the largest available square number need not find four terms: for it chooses , while uses four. The appeal of the theorem is this gap between local choices and a global promise: individual square numbers become farther apart, and two or three terms leave arithmetic obstructions, yet four terms cover every nonnegative integer.
For historical orientation, Conrad dates Lagrange's four-square theorem to and identifies the memoir as Démonstration d'un théorème d'arithmétique: it appeared in the Berlin Academy's volume for the year , published in , pages –. Keeping the volume year and publication year distinct avoids an apparent conflict between dates. [ref]
A short proof outline connects Gauss's lemma to counting points with integer coordinates. For distinct odd primes , define the two floor function sums
The parity form of Gauss's lemma gives and . In the open rectangle , , the line separates points below it from points above it. None lies on the line, because and coprimality would force . The total is therefore . Combining that count with the parity identities gives quadratic reciprocity.[ref]
Figure 1.
A line partitions the integer coordinate points behind the quadratic reciprocity exponent
. For , the counts are ; for , they are . Dashed edges mark the excluded boundary of the rectangle. This illustrates the counting step; the separate parity step from Gauss's lemma is essential to relate the count to Legendre symbols. Details.
A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers and , and take complete sorting records whose sort keys satisfy . Use exactly positions in positional notation with radix , including leading zeros. At pass , apply a stable digit sort to the current array using
The floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.
For an original input, let the letters identify the attached data:
Here , , and leading zeros only align place values; represents the integer five. The exact pass ledger is:
After the units pass, the numerical digits are . The ties retain before and before before . This array is not yet ordered by its whole integer sort keys: still precedes . After the tens pass, the two-position suffixes are . In particular, now precedes : their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.
Figure 1.
Three stable digit passes order successively longer suffixes
. Original decimal radix sort ledger. Each card carries an unchanged record label. Orange marks the numerical digit read in the current pass; green marks lower positions already processed. The suffix row beneath each pass shows precisely what is ordered, rather than claiming whole-key sortedness early. Details.
Legendre's formula Created 2026-10-14 Updated 2026-11-05
For a nonnegative integer and a prime number , the Legendre formula computes the prime exponent in a factorial without forming that huge product:
Here is the floor function. The sum is finite: every term with is zero. When , all terms vanish, agreeing with and . The prime number hypothesis matters: a composite number does not give the same p-adic valuation or additive prime exponent. For example, the floor sum with is one, whereas divides .
Why count multiples repeatedly? Each multiple of in contributes one factor of ; each multiple of contributes another; and so on. A factor with p-adic valuation occurs in exactly the first counts. Adding those contributions proves the formula.[ref]
For the original example ,
The five multiples each contribute a second factor of three. The factor contributes a third, so it appears in all three rows. Equivalently, among there are eleven factors of p-adic valuation one, four of valuation two, and one of valuation three: . Thus divides , while does not.
Figure 1.
Nested multiples count the factors of three in
. Each colored cell contributes one to the p-adic valuation. Multiples of nine occur in two rows, and occurs in three. Summing by rows gives ; summing by columns gives . Factors not divisible by three contribute zero and are omitted. Details.
Repeated Euclidean division provides a practical evaluation: replace by , starting from , and add each new quotient until it is zero. This uses only the successive quotients for the example. The same calculation handles divisibility of binomial coefficients, where the p-adic valuations of the denominator factorials are subtracted.
Lossy block averaging 2026-10-13
This toy image compression method stores one rounded arithmetic mean for each disjoint block of grayscale pixels. The quantization rule is round to the nearest integer, with exact halves rounded upward. Each stored value is an unsigned eight-bit integer. Reconstruction fills the original block with that value, a form of nearest-neighbor interpolation. Averaging already discards information; rounding can discard more.
Here is an exact source array. Index rows and columns by and define
The floor function makes constant within each block; the indicator function adds 1 only to its upper-left pixel. All values are integers from 20 to 215. Each block therefore has the exact form
For example, the upper-left block has arithmetic mean and is stored as 40. The block immediately to its right is stored as 52. The complete stored array is specified by for . Its first row is ; its last is .
This toy file format again has eight-bit width and height fields followed by a one-bit mode: 0 means raw eight-bit grayscale pixels, 1 means the rounded block arithmetic means. This profile accepts only width and height 16. The decoder knows the block size and reconstruction rule from the format, reads the 64 stored values in row order, and repeats each across its corresponding block. The original 256 pixels cost payload bits; the 64 stored values cost payload bits. The reduction is . These payload counts exclude the common 17-bit file header; complete sizes are 2065 and 529 bits, or 2072 and 536 bits after final zero padding to eight-bit units. There is no stored codebook or additional prediction rule.
The empirical mean squared error averages squared differences over the 256 original pixel positions:
Every block has the same four errors, so this value is exact in squared stored shade units. If the unrounded arithmetic mean could be reconstructed, the error would instead be ; eight-bit quantization adds . That hypothetical comparison does not count fractional means as free eight-bit values.
The broad shade pattern survives, while the alternating bright and dark pixels vanish. Indeed, a second source with every block constant at produces the identical stored array : exact decoding of both sources is impossible. This makes the storage benefit and the lost detail visible at once. Block averaging is useful for a coarse preview when the individual pixels are dispensable; choosing an acceptable mean squared error or visual result is part of the application, not a guarantee supplied by the encoder.
Figure 1.
Rounded 2 by 2 block means reduce the payload by 75 percent while destroying fine detail
. Details.
Mantel theorem Created 2026-09-24 Updated 2026-10-14
The complete bipartite graph has vertex sets and , with every edge between and and none inside either part. Its six vertices support edges and no triangles in a graph: among any three vertices, two belong to the same independent set and have no joining edge.
Figure 1.
The sharp nine-edge triangle-free graph and the three triangles in a graph created by adding
. Details.
Add the single edge . Each is a common neighbour of its endpoints, producing the triangle in a graph . These are exactly the three new triangles in a graph, because every triangle in a graph must use the only edge inside a part. The new count is ten edges; nine was the last possible count without a triangle in a graph on six vertices.
In general, every simple graph with a finite set of vertices that is triangle-free has at most
edges. This is the case of Turán's theorem, with forbidden clique . Equality holds exactly for the balanced complete bipartite graph , up to graph isomorphism; empty parts are allowed for .[ref]
The floor function gives the exact integer bound. Splitting vertices into two independent sets of sizes and , and putting in every cross edge, gives
The count is largest when is an integer nearest . For it is ; for it is . Both equal . This proves attainability for every , including the empty graph.
A short proof of the upper bound uses degrees of vertices. In a triangle-free graph, the endpoints of an edge have disjoint vertex neighbourhoods: a common neighbour would complete a triangle in a graph. Thus . Summing over edges counts once for each of the edges incident to , giving
For , the Cauchy-Schwarz inequality and handshaking lemma yield
If , division gives ; is immediate. Since is an integer, apply the floor function. The case is immediate too. This proves the bound; the full equality characterization follows from Turán's theorem.
The useful reversal is that more than edges force a triangle in a graph, whatever their placement. A global count certifies a local pattern. The extremizer is bipartite, but a triangle-free graph need not be bipartite: a five-vertex graph cycle has five edges, below the bound of six. Historically, Willem Mantel posed the triangle-exclusion question in 1907.[ref]
Let be the memory page size, the aligned starting file offset, the mapping length and its base virtual address. A valid displacement with corresponds to file offset
Here is the relative memory page index, the floor function selects its integer part, and Euclidean division gives the within-page displacement . The backing page begins at . This identifies file contents; the page table separately selects a resident page frame and enforces permissions.
Take , and bytes in a file of at least 12288 bytes. A has a shared file mapping at . B has a shared file mapping at and a private file mapping at . These bases are illustrative chosen results, not requested fixed addresses. All three mappings cover the same two backing pages: file offsets 4096–8191 and 8192–12287. Displacement selects relative page 1, within-page displacement 37 and file offset . Thus A's 0x10001025, B's shared 0x20001025 and B's private 0x30001025 initially identify the same byte. The adjacent displacement 4134 identifies file offset 8230. Different virtual addresses can reach the same backing contents.
Figure 1.
Two operating-system processes map two backing pages at different virtual addresses; displacement 4133 identifies file offset 8229
. Details.
To access a requested file offset that is not aligned, choose and displacement . Mapping enough bytes to cover that displacement plus the requested length makes the desired data start inside the aligned mapping. Do not pass the unaligned directly as the Linux kernel mmap offset. For example, uses and displacement 37; that one-page start differs from our two-page mapping's .
Merge sort Created 2026-10-13 Updated 2026-10-18
Merge sort is a divide-and-conquer algorithm that sorts a finite array by splitting it into contiguous halves, sorting each half using recursion, and combining the two sorted arrays with the merge algorithm. An empty or one-entry array is returned immediately. For length , put the first entries on the left and the remaining on the right; the brackets are the floor function and ceiling function. Always choose the left head on equal keys to obtain stable sorting. This is the split, sort, combine structure taught in the MIT lecture notes.[ref]
Take the concrete input array
The tags identify the entries originally at indices and , counting from zero. Both keys are ; the tags are never compared. Reading downward in the figure follows the splits, then the returned sorted arrays. Arrows show dependencies; the level layout groups independent calls rather than giving their chronological execution order.
Figure 1.
Merge sort splits into base cases and returns sorted arrays
. The tagged keys 2a and 2b retain their original order through stable sorting. The merge algorithm makes 4, 6 and 7 head comparisons on the three returning levels, for 17 in total. Details.
The first two halves are and . Their pairs split into one-entry base cases. Applying the merge algorithm gives the following fully worked return levels; each number in the last column counts only comparisons between two available heads.
Returning levelResulting sorted arraysHead comparisons
Pairs, , ,
Halves,
Whole array
In the left-half merge algorithm, the head pairs are , and ; it takes , then appends . In the final merge algorithm, the head pairs are , , , , , and . It takes , then appends . Thus this precise version makes head comparisons and, ignoring identity tags, returns .
The elegance of merge sort is that it creates exactly the structure its next step needs: two smaller sorted arrays make the larger ordering inexpensive. Once the whole array is sorted, equal keys are adjacent and binary search can serve repeated queries. Stable sorting also retains information that the keys alone do not express. If the left-half merge algorithm instead takes the right head on the tie, it returns ; the keys are sorted but stable sorting has failed.
For time complexity, assume each key comparison, entry access and entry copy has constant cost. The merge algorithm processes entries in time. In Big O notation, the resulting recurrence relation is
For , the balanced levels contain entries each and there are returning levels. Each costs , so the worst-case time complexity is . For arbitrary , there are at most returning levels, each processing at most entries, giving the same bound. The worst-case number of head comparisons is also . Here is the base-two logarithm. The MIT notes give this level-by-level analysis for merge sort.[ref]
The conventional array implementation uses a reusable buffer of entries for the merge algorithm, together with pending calls for recursion. Its auxiliary space complexity is therefore , beyond the original array. This bound describes that implementation. A linked list permits a merge algorithm that reconnects existing nodes; its storage accounting differs from copying array entries into a buffer.
For a short algorithm correctness outline, the empty and one-entry base cases are sorted. Assuming recursion correctly sorts both shorter halves, the merge algorithm returns all their entries in order. Equal keys within a half keep their relative order by the same argument applied to the smaller call; across halves, every left entry originally preceded every right entry, so taking left first preserves stable sorting. Both half-lengths decrease for , establishing termination.
Mertens bound from a log-integrable Chebyshev error Created 2026-10-07 Updated 2026-11-05
Let be the second Chebyshev function. Suppose
Then the Mertens function satisfies for .
First, the Möbius divisor-sum identity gives . Replacing each floor function by its input with error at most one shows . The exact Dirichlet convolution identity , with the Von Mangoldt function, now gives
Indeed, the main term is . The error is at most a constant times . On each interval where , the harmonic sum of is bounded by an absolute constant, so the assumed convergence of the series bounds the total error by .
Finally,
because by integral comparison. The classical Prime number theorem error satisfies the dyadic condition. Thus the Mertens function estimate follows directly from the second Chebyshev function error, without a separate bound for the reciprocal Riemann zeta function.