Additive function continuous at one point is linear Created 2026-10-14 Updated 2026-10-18
A real additive function that is continuous at one point is continuous everywhere and has form . Indeed , and as . Then for every . Additivity gives for every rational number; continuity and the density of the rational numbers extend this identity to every real argument.
The step from the rational numbers to the real numbers can be made explicit. Put . For an arbitrary real number , the density of the rational numbers supplies a sequence of rational numbers . Because continuity at the original point already implied continuity everywhere,
This is where continuity enters: knowing all the rational values alone does not justify the first equality.
For an original numerical example, use the floor function to define the rational lower approximants . They obey . When and is continuous at one point, rational homogeneity of an additive function and the preceding argument give
The error bound here follows from the resulting linear map, rather than from a quantitative bound on the initially assumed continuity.
Figure 1.
Continuity connects exact rational values to an irrational limit; either one-point continuity or boundedness on an interval forces f(x)=xf(1)
. Details.
Dropping either condition destroys the implication. The increasing sequence has a lower bound one but no upper bound, and no finite limit of a sequence. For any real threshold , the Archimedean property gives an index , and monotonicity gives for all . Its divergence to in the extended real number line is different from convergence to a real number.
Conversely, is a bounded sequence, with , but is not a monotone sequence and has no limit of a sequence. Its subsequence at even integers is constantly one, and its subsequence at odd integers is constantly minus one. These two subsequential limits cannot both equal a single limit of a sequence. [ref]
Figure 1.
Neither monotonicity alone nor boundedness alone ensures a finite limit of a sequence
. Left: is increasing but unbounded above. Right: stays in but alternates between two distinct subsequential limits. Both plots show finitely many terms; the formulas and the arguments establish the counterexamples for all indices. Details.
The ambient real numbers also matter. An original example using the floor function is
Every is a rational number, because , and
The strict lower inequality uses the irrationality of the square root of two. Hence this bounded sequence converges to in the real numbers, but has no limit of a sequence in the rational numbers. Convergence to a rational candidate would also be convergence in the real numbers, contradicting uniqueness of the limit of a sequence. The formulas give , , , : this counterexample even has a plateau. This illustrates why completeness of the real numbers matters: the rational numbers lack the least-upper-bound property needed to contain the required supremum. [ref]
Benford law from logarithmic uniformity Created 2026-10-07 Updated 2026-10-14
For a positive random variable , write its base-ten logarithm as an integer part plus a fractional part:
The floor function handles values below one as well: for , and the decimal significand is . Since , the first nonzero decimal digit is . The monotonicity of the logarithm gives the exact event equivalence
If has the uniform distribution on , the probability of this interval is its length. Consequently , proving the Benford law. This argument assumes uniformity of the fractional part of the logarithm, rather than uniformity of itself. See the logarithmic-coordinate explanation in Peter Sheridan Dodds, Benford's Law, essential story.
Figure 1.
Leading-digit intervals have unequal lengths in the fractional logarithm and equal lengths in the original number
. Details.
An exact constructed example is the log-uniform distribution on , with probability density function there and zero elsewhere. Its total mass is . The change of variables formula with gives for . Equivalently, integrating directly gives
For example, the probability of first digit four is . By contrast, an ordinary uniform distribution for on has probability density function there, so for every digit. This is a concrete counterexample to any claim that the Benford law holds for every positive random variable.
More generally, a log-uniform distribution on with has uniform on . If its logarithmic span is a positive integer, reduction to the fractional part wraps an interval of length around the unit interval exactly times, making uniform even when is not a power of ten. Arbitrary partial-decade truncations generally do not have this property: for a log-uniform distribution on , the first digit is always one.
Under the uniform fractional-logarithm assumption, multiplication by any constant replaces by . This is a rotation modulo one, which preserves the uniform distribution and therefore preserves the Benford law; see scale invariance of decimal significands. For the constructed example, multiplying by gives a log-uniform distribution on with the same digit probabilities. The claim concerns the decimal significand law: there is no proper probability density function proportional to over all of , since its integral diverges. The existing scale-invariant prior describes that unnormalizable measure, while a finite log-uniform distribution is normalizable.
Keep an array unchanged, and sum entries in the half-open integer interval of array indices . The precondition requires integers 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:
S(A, l, r):
    require integer indices with 0 <= l <= r <= length(A)
    size = r - l
    if size == 0:
        return 0
    if size == 1:
        return A[l]
    middle = l + floor(size / 2)
    left_sum = S(A, l, middle)
    right_sum = S(A, middle, r)
    return left_sum + right_sum
For the original array , call . The left half returns , the right half returns , and the original invocation returns . The right half's left endpoint increases from zero to two: what decreases is range length , not every argument. Negative entries affect the answer but do not affect algorithm termination.
Figure 1.
Seven calls compute an array sum with only three frames active at once
. Original binary tree of invocations for , with integer intervals labeling ranges and upward arrows labeling returned sums. Small numbers give the order in which invocations begin when the left child runs first. The highlighted graph path contains the three active stack frames while the entry is read; the result from the completed left sibling is retained by its parent. Details.
For range length , the children have lengths and , both positive and strictly less than . 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 : 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 , the invocation tree is a full binary tree with leaves, one per array entry. If is its number of nonleaf vertices, counting edges gives , so . Thus the total invocation count is , and there are combining additions. Here gives seven calls and three combining additions. For , there is one call and no combining addition; for , there is also one call and no combining addition, but no entry leaf, so the 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 for , and one for . Balanced splitting therefore needs frames for , compared with the frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is and its auxiliary space complexity is machine words for , 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.
Binary expansion Created 2026-09-24 Updated 2026-11-05
Every real number has a binary expansion
For , construct it by repeated doubling. Set , then and , using the floor function. Each remainder stays in , and induction gives
The remaining error is less than , so the finite partial sums converge to . For , choose every binary digit equal to one and use the geometric series.
Figure 1.
Successive binary digits refine an interval around
. Each blue interval runs from the th partial sum to . Filled left endpoints are included and open right endpoints are excluded. The red line marks ; the labels show its successive binary prefixes. Each new digit halves the remaining interval's length. Details.
An expansion need not be unique: . For , this ambiguity occurs precisely at the dyadic rationals, through a terminating expansion and an alternative ending in ones. At the endpoints, the displayed purely fractional form uses all zeros for zero and all ones for one. A general nonnegative real number is represented by adding the finite binary representation of its floor to an expansion of its fractional part; a negative real number is handled by a separate sign. In that broader notation, too.
Binary heap Created 2026-10-13 Updated 2026-10-24
A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.
The complete binary tree can be stored directly in a zero-indexed array : read its levels from top to bottom, left to right. The root of a tree is at index . The possible children in a rooted tree of index are at and , and an index denotes a present entry only when it is less than . For , its parent in a rooted tree is at , using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.
Consider
The children in a rooted tree of index have keys ; those of index have keys ; those of index have keys . The six comparisons , , , , , establish the heap order. At index , the parent in a rooted tree is index , carrying key .
Figure 1. . Matching indices identify the same entries in both representations. The heap order compares each parent in a rooted tree with its children in a rooted tree; it does not make a sorted array. Details.
The array is visibly not a sorted array: precedes , and precedes . Nor is the last entry a maximum: it is , whereas the maximum is at index . The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return , a minimum, without inspecting the other entries.
Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key into the displayed binary heap. It is appended at index , and exchanges with indices , , then :
The moving key follows ; the keys each move down one level. Only this chain needs repair.
Now apply extract-min. Save key , move the last key to the root of a tree, and shorten the array to length . Use sift down, always choosing the smaller of the present children in a rooted tree:
First exchanges with key at index , since ; then with key at index , since . At index , the possible children in a rooted tree would be indices , both outside the shortened array, so the process stops. The returned key is , and the remaining binary heap is exactly the original one.
Figure 2.
Sift up inserts 1, then sift down restores the original binary heap after removing 1
. The four panels show the start and end of each repair. Colored arrows mark the moving key's graph path. The extraction panels contain seven entries: index 3 has no children in a rooted tree. Details.
For a nonempty binary heap with entries, the deepest level is , using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:
OperationTime complexityReason
peekRead the root of a tree.
Insert for Append, then sift up through at most the levels of the complete binary tree.
extract-min for Move the last entry, then sift down through at most those levels.
Build from an arbitrary arrayApply sift down from the last index with children in a rooted tree back to index .
These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.
To build a binary heap, begin at index and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives work, rather than charging to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.[ref]
The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes time for . An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.
The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives , so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.
Binary search 2026-10-13
Binary search finds a target in a sorted array by inspecting the middle of the remaining candidate range. If the middle entry is smaller than , every entry to its left is also too small; if larger, every entry to its right is too large. One comparison therefore rules out many entries. Equal entries are allowed; this version returns any matching index, without promising the first occurrence.
Use indices starting at zero and inclusive endpoints . Initially , , where is the array length. While , choose
The brackets denote the floor function. Compare with : return on equality; set if ; otherwise set . If , report absence. The updates exclude the already inspected middle entry. This also handles an empty array, whose initial endpoints are . Sedgewick and Wayne specify a sorted array as input and return a matching index or for absence.[ref]
For a fully worked example, take the sorted array
Search for :
StepCandidate indicesMiddle index and valueConsequence
1, : retain .
2, : retain .
3, Return index .
For , the first two steps agree. Next retains only index ; inspecting sets . Now , so the answer is "absent" after four comparisons.
Figure 1.
Binary search retains only candidates compatible with every comparison
. Blue cells are current candidates, orange marks the middle entry, and green marks a match. Both searches use the same fifteen-entry sorted array. Details.
The loop invariant is: the array stays sorted, , and every index containing lies between and . It holds initially. The sorted array property justifies each exclusion. Returning on equality gives a match; an empty candidate range implies absence. Crucially, this loop invariant allows to be absent from the beginning.
For a nonempty range of size , an unsuccessful comparison leaves at most candidates. Thus sizes satisfy after unsuccessful comparisons. This proves termination and, for , at most middle-entry comparisons. The final singleton still needs inspection: requires one comparison, not zero. For , the bound is four. This is the halving argument behind logarithmic time complexity.[ref]
A decision tree with binary tests has at most leaves. Distinguishing possible matching positions therefore requires . This lower bound counts binary tests, whereas the bound above counts three-way comparisons.
The rational numbers lie in and obey . They form a convergent sequence in the real numbers, with limit of a sequence . Every subsequence has that same real limit. Because is an irrational number, no subsequence converges to a point in the rational numbers with their usual metric. Boundedness alone therefore does not give the corresponding theorem in every metric space; completeness of the real numbers is doing real work here. The floor function simply truncates the decimal expansion in this example.
Cache line Created 2026-10-13 Updated 2026-10-24
A fixed-sized, aligned block of consecutive bytes transferred and tracked as a unit by a data memory cache. Here cache line and cache block name that unit of data, including its identity in backing computer memory; a resident slot holds a copy. Reading one element can bring neighbouring elements into the same cache line, exploiting spatial locality.
For a nonnegative integer physical address and a cache line size bytes, Euclidean division gives the backing cache block number and offset :
Here the brackets denote the floor function and gives the remainder. Cache line contains bytes at physical addresses through . With , read address 52 selects cache block 3, spanning addresses 48–63, and offset 4. Addresses 48 and 52 therefore request the same cache line; addresses 15 and 16 request different cache lines despite being adjacent.
Figure 1.
Physical address 52 selects cache line 3 and offset 4; the resident copy occupies cache slot 0
. Details.
For a cache line size , the low bits give the offset. In a fully associative cache, all remaining bits identify the backing cache block as its cache tag; there are no address bits selecting a particular cache slot. An eight-bit illustration gives : four bits 0011 for cache block 3 and four bits 0100 for offset 4 in the binary numeral system. The eight-bit width is illustrative; the trace does not assume an actual eight-bit machine. [ref]
Distinguish this identity from a cache slot, which can hold different cache blocks over time. After read nine in the memory cache example, cache slot 0 contains cache line 3 and cache slot 1 contains cache line 0. Their cache tags identify 3 and 0; neither cache line number is its slot number. Some texts use “cache line” for the storage entry itself; this article reserves cache slot for that role.
Cache tag 2026-10-14
Metadata identifying which eligible backing cache block a valid cache slot currently holds. In the fully associative cache example, the cache tag is the full cache block number ; in the two-slot direct-mapped cache example, the slot supplies and the cache tag can store using the floor function.
Ceiling function Created 2026-10-14 Updated 2026-10-20
The ceiling function gives the least integer large enough to meet a real lower bound. For a real number ,
Thus , , and . The operation rounds upward in the total order on the real numbers, which can move a negative input towards zero. Its difference from the input obeys . Python's math.ceil implements this least-integer definition. [ref].
The ceiling count for fixed-size batches is a direct application. Suppose each box holds at most items, with positive integer , and there are items. The smallest number of boxes with enough capacity is : a candidate count must satisfy . For , , six boxes are needed, leaving unused places. Exactly 100 items need only five boxes, and zero items need zero boxes. Adding one to the floor function result unconditionally would therefore overcount at exact multiples of .
Figure 1.
The ceiling function retains the endpoint on the left and counts enough whole containers
. Left: open and filled endpoints distinguish the half-open intervals where , including negative inputs. Right: the original capacity example uses 20 items per box; 101 items need six boxes, while an exact multiple of 20 needs no extra box. The right-hand inputs are integer item counts. Details.
For nonnegative integer and positive integer , Euclidean division gives the exact identity
Write , . The count is when the remainder is zero and otherwise, and the right-hand side encodes these two cases. This argument specifies the domain of the identity; arbitrary negative denominators require their own sign conventions.
The ceiling function is a nondecreasing function, constant on each of the half-open intervals , and has a discontinuity of a function at every integer. It is tied to the floor function by . Adding an integer shifts its output by the same amount: . At an integer the floor and ceiling agree; at every other input they differ by one. These statements refer to exact real numbers; an input already perturbed by floating-point arithmetic can land on the other side of a threshold.
Chebyshev function Created 2026-09-28 Updated 2026-11-05
The two Chebyshev functions measure the total natural logarithm weight of prime numbers or of prime powers greater than one below a real cutoff :
Here ranges over prime numbers, over positive integers, and over positive integers. The Chebyshev theta function , also written , weights each prime number once. The second Chebyshev function weights every positive power of each prime number separately. Both vanish for ; the inclusive cutoff makes them right-continuous functions and nondecreasing functions, constant between their jumps. [ref]
At , the prime numbers are , while the extra prime powers greater than one are . Exactly,
At each prime number , both Chebyshev functions jump by . At a prime power with , only the second Chebyshev function jumps, by . At and neither jumps. Notice that the gap is already positive at and : a shared jump does not remove the earlier contribution from .
Figure 1.
The Chebyshev functions separate at the extra prime powers , , and
. The upper panel compares and for . Solid endpoints include the jump at each contributing integer; open endpoints show the preceding value. The lower panel isolates , which jumps by at and and by at , reaching . All logarithms are natural logarithms. Details.
Grouping the prime powers by their exponent gives, for ,
The floor function cutoff is exact: forces whenever . For each exponent, is equivalent to . An upper cutoff smaller than the lower one means an empty sum. [ref]
Any deterministic comparison sort correct for all orders of distinct sort keys needs at least comparisons on some input. Here is a factorial, a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.[ref]
For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries . Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.
Figure 1.
A comparison decision tree distinguishes the six orders of three distinct sort keys
. Each internal node tests the sort keys of two fixed original entries. A leaf gives the order in which their complete sorting records must be emitted. There are leaves and maximum depth three. The diagram assumes distinct sort keys, so no equality branch is needed. Details.
For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least leaves. Maximum depth permits at most leaves, so gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.
The growth follows without a precise approximation to the factorial. At least of its factors are at least , so for ,
The brackets denote the floor function. This gives a constant times lower bound for large , matching the worst-case comparison growth of merge sort.
Distinct sort keys are essential to the counting argument. Identical sort keys do not create different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.
Convolution dilation 2026-11-05
Convolution dilation specifies the spacing between neighboring kernel sample points in a convolutional layer. Dilation one samples adjacent positions; larger dilation separates those positions while keeping the filter's learned coefficient count fixed. Convolution stride instead controls the spacing between successive filter origins.[ref]
For an own real one-dimensional example, take
and coefficients , with stride one, no padding and no bias. Use the unflipped cross-correlation convention. Dilation one sums three adjacent values and gives . Dilation two instead uses offsets :
The second filter evaluates a wider input span while still using three coefficients.
For sampled coefficients separated by positions, the first-to-last displacement is . Including the first position gives the effective convolution kernel size
Thus spans five positions. At each origin only three of those five positions are sampled directly.
The same linear operation can be represented by a dense width-five kernel . The inserted zeros are fixed structure, not additional trainable coefficients. Dilation changes the footprint without making the original three-parameter filter a general five-parameter one.[ref]
For input length , symmetric zero padding and stride , the usual per-axis size formula becomes
when the padded input accommodates the footprint. The example gives outputs. The floor function counts origins whose final sample remains in range.[ref]
Dilation can enlarge a unit's spatial neural network receptive field without evaluating every intervening input position. Whether later layers fill those gaps depends on the architecture. A wider span alone does not establish greater numerical influence at every position or better performance on a learning task.
Convolution stride 2026-11-05
The convolution stride specifies how far the filter's origin advances between neighboring output positions of a convolutional layer. It controls which spatial positions are evaluated. A larger stride usually produces a smaller output grid without changing the number of coefficients in each filter.[ref]
For a real one-dimensional example, take the input
and a size-three all-ones filter, no bias and no padding. Using the unflipped cross-correlation convention, stride one evaluates windows beginning at indices and gives
Stride two evaluates windows beginning at indices , giving
The second result keeps every second origin from this first grid; it still combines three input values for each retained origin.
For an undilated length- input and length- filter, no padding and stride , a zero-indexed output uses input indices through . Requiring its last index not to exceed gives . Counting the admissible nonnegative integers therefore gives
when and is a positive integer. The floor function is essential when the last candidate origin would extend beyond the input.
With symmetric zero padding of positions per side and convolution dilation , the corresponding standard shape expression is
Here dilation changes the spacing of samples within a filter footprint; stride changes the spacing between filter origins. The two parameters have different roles.[ref]
For two-dimensional data, specify a stride for each spatial axis; unequal strides need not reduce height and width by the same amount. The weights of the filter remain shared across the visited positions. Stride also changes how neighboring outputs' neural network receptive fields are spaced in the original input, so it affects more than just a displayed array size.
Cyclic logarithmic coloring Created 2026-10-05 Updated 2026-10-14
For and an integer , assign the color . The floor function partitions the domain into half-open geometric bins. If , their bin indices differ by an integer in , so their colors differ. For example, and separates every ratio in . Composing this finite coloring with another logarithm can obstruct monochromatic multiplicative configurations whose logarithms have such ratios.
Decimal significand 2026-10-14
For , the decimal significand is the unique such that for an integer . Explicitly, and , using the floor function and the fractional part. For , and , the decimal significand is and the first nonzero digit is . In the classical terminology of logarithm tables, the logarithmic mantissa is , which differs from the decimal significand .
Dirichlet hyperbola method Created 2026-09-24 Updated 2026-10-14
The Dirichlet hyperbola method turns a long summation over a Dirichlet convolution into two short ones by covering the lattice points below a hyperbola with two overlapping strips. Its simplest application is an exact count: for a positive integer , every positive integer divisor of corresponds to the ordered pair . Thus the divisor summatory function counts precisely the ordered pairs of positive integers with :
Here is the divisor function, and the floor function gives the number of allowed values of for each . The axes are excluded, while points on are included.
Set , using the floor function and the positive square root. Every counted pair has or . Otherwise . The first strip contains points; swapping the two coordinates gives the same count for the second. Their overlap contains all pairs with , since . The inclusion-exclusion principle therefore gives the exact identity
The subtraction is for the whole overlap square, rather than only the diagonal. The same Dirichlet hyperbola method identity holds for real , with and . [ref]
Figure 1.
The Dirichlet hyperbola method counts 35 positive lattice points with : two strips of 22 points overlap in a square of nine points
. Details.
The effective convolution kernel size is the bounding extent of a dilated convolution kernel along a spatial axis. For sampled coefficients with convolution dilation , their offsets are . The first-to-last displacement is , so including the first position gives
This extent determines the kernel footprint used in spatial shape calculations; it is not generally the number of coefficients.[ref]
For a two-dimensional example, choose a sampled kernel shape with dilation . Its row offsets are and column offsets are . The bounding shape is therefore
There are six sampled spatial positions inside a twenty-position bounding box. Fourteen intermediate positions are absent from the sampling pattern.
With three input neural network channels and four output channels, ordinary dense channel connectivity uses
weights and optionally four biases, giving parameters. A general dense five-by-four kernel with the same channel counts would have weights. Representing the dilated operation that way would require of them to be fixed zeros, rather than independently learned parameters.[ref]
For an unpadded -by- input and convolution stride one, the output grid is
More generally, for one axis with symmetric zero padding and stride ,
when the padded input accommodates the footprint. The floor function counts admissible filter origins.[ref]
The effective size is a geometric quantity for one layer. The complete neural network receptive field through several layers additionally depends on their kernels, strides and connections. Likewise, changing stride moves the spacing of origins; changing dilation changes the footprint at each origin. Keeping bounding extent, sampled-position count and learned-parameter count separate avoids confusing three different sizes.