Min_25 sieve Created 2026-10-20 Updated 2026-11-05
The Min_25 sieve computes summatory multiplicative functions by isolating weighted prime sums and then restoring composite contributions. A useful basic form applies when for primes , the degree is small, and values on prime powers can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.[ref]
Use quotient arguments . There are distinct values: indices at most contribute that many, and larger indices yield values below . The floor function identity keeps later quotients in this table.
For each exponent , initialize . Process primes in increasing order, and eligible in decreasing order, applying
This removes composites whose smallest prime factor is . The subtraction inside parentheses excludes earlier primes from the possible cofactors. Decreasing ensures each smaller argument still has its pre- value. After sieving, is the desired sum of over primes up to .
To restore composites, let be the th prime and let sum over with every prime factor greater than . Set for . Otherwise its prime contribution is , and add
Unique decomposition by smallest prime factor and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With , and , the answer is . No complete-multiplicativity assumption is needed.
For the Euler totient function up to six, the prime contribution is . The composites add , and gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.
Natural density Created 2026-10-05 Updated 2026-10-13
For a set of nonnegative integers, its natural density is the limiting proportion of the first nonnegative integers that belong to :
provided this limit exists. Write for the counting function. The numerator is a finite cardinality; the denominator is exactly , including zero. Every existing natural density lies between zero and one.
For the even nonnegative integers , there are elements below and below . Thus using the ceiling function, and . For the square numbers , the exact count for is
The floor function counts the allowed indices , and the extra one counts zero. At , the square numbers below ten are , so the proportion is ; at , it is . The count grows like the square root of , while the denominator grows like .
The prime numbers also have natural density zero. If is their set, the Prime number theorem gives , hence . The Prime number theorem is a substantial result about the count, rather than a consequence of the fact that there are infinitely many prime numbers. [ref]
Why use natural density when cardinality already measures size? The even nonnegative integers, the square numbers, and the prime numbers all have the same countably infinite cardinality, yet their proportions among large initial integer intervals differ. Natural density distinguishes frequent membership from sparse membership. Equivalently, under a uniform distribution on a finite set of possible nonnegative integers, is the probability of landing in . A set without natural density shows why this limiting proportion need not exist.
Figure 1.
Exact proportions below N: even integers, squares, and an alternating-block set
. Every point uses the count in divided by , with zero included among the even integers and square numbers. The right panel marks exact block-boundary counts for a set without natural density. Its low and high proportions approach and along different subsequences. Details.
Paging 2026-10-13
Paging divides an address space into fixed-size memory pages and main computer memory into equally sized page frames. Here assume byte addressing, one memory page size bytes, and an unsigned virtual address . Its virtual page number and offset are
The brackets denote the floor function, and gives the remainder in Euclidean division. If the page table maps to physical frame number and permits the access, the physical address is
The low bits are unchanged; the other bits select the memory page or page frame. A bit shift and bit mask can extract these fields. [ref]
For a 16-bit virtual address and bytes, take in hexadecimal. Then and . A mapping to gives
Thus the eight high bits choose a mapping; the eight low bits choose the same position in the resulting page frame. The 256-byte size is for illustration, not a claim about an actual architecture's supported memory page sizes.
Figure 1.
Translating 0x1234 through an illustrative page table, with a separate offset and access check
. Details.
The useful freedom is that adjacent memory pages can occupy unrelated page frames. In the diagram, virtual pages 0x12 and 0x13 occupy page frames 0x07 and 0x02; virtual addresses 0x12ff and 0x1300 are consecutive, but translate to physical addresses 0x07ff and 0x0200. Uniform units simplify placement and page replacement, at the cost of page table storage and unused bytes within partly filled memory pages. For example, placing 300 bytes in exclusive 256-byte page frames requires two page frames, leaving bytes unused.
Pairing function Created 2026-10-03 Updated 2026-10-14
A pairing function is a computable function that gives a bijection from the Cartesian product to , with two computable functions recovering its coordinates. Here consists of the natural numbers, including zero. If is the pairing function and its decoding functions, the requirements are
Every ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.
The Cantor pairing function makes this concrete through triangular numbers:
On the diagonal , list . There are ordered pairs there, and ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from through . These intervals touch without overlapping and cover all natural numbers; within each interval the offset determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.[ref]
For example, the Cantor pairing function gives
The order of the coordinates matters: and are different ordered pairs with different codes.
Figure 1.
The Cantor pairing function on a finite window: labels are codes, and the first 21 ordered pairs fill diagonals zero through five
. Details.
To decode a natural number , find the unique diagonal index satisfying
The inequality gives , so both recovered coordinates are natural numbers. At , , hence , , and . At , and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expression
This is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large . Use an exact integer square root instead: with computed using integer arithmetic, . Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.
A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with binary digits has possible values, while two such words have possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product . Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.
Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes as
Decode the outer ordered pair first: gives . Decode its first coordinate to recover , giving the nested ordered pair and thus the original tuple .
Figure 2.
Decoding a known three-entry tuple: first unpair 257 into (18, 4), then unpair 18 into (2, 3)
. Details.
The tuple length and nesting convention must be known. The same code represents as a two-entry tuple and as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.
A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.[ref]
Yes: starting from zero, increments of the decimal counter cost digit changes, uniformly in the number of digits. An increment changes the trailing digits equal to into and increases the next digit. Number digits from at the least significant end. Digit changes once every increments, so the exact number of changes is
Here the floor function counts carries reaching each position, and the last equality sums a geometric series. Since digit changes on every increment, for . The loop tests and carry handling add only a constant amount per changed digit and per operation, giving the same time complexity.
An accounting method explanation is also possible. Charge two credits for each change of digit : one pays for that change and one joins a common bank. For increments the higher digits change at most times, so their costs can be covered from that bank; the displayed prefix bound ensures that it never goes negative.
The formula allows wraparound modulo ; alternatively, restrict to increments before overflow. Initializing the array itself costs if that is counted separately. If the initial digits are arbitrary, the number of changes at position is at most , giving in Big O notation. Starting with all digits equal to makes the first increment cost , so the initial-state convention matters.
For an initially zero binary counter, bit changes precisely on increments whose indices are divisible by . Weighting each such change by gives the exact total
For and , put . All summands with vanish; each of the other summands is at most . Therefore
This is sharper than simply charging for each of all positions when is small. To show that the order is best possible, use for . For every ,
Thus the asymptotic analysis gives a tight bound. If wraparound is excluded, , and this becomes , often written for . If wraparound is allowed and , it becomes . For , the cost is zero.
For completeness, the same conclusion cannot be asserted uniformly over arbitrary initial binary counter states. An initial value makes the first increment change every bit, costing . A general upper bound follows by replacing each floor function in the count by a ceiling function:
To see the second inequality, split at : for , use , and for , use . For the worst initial-state cost is consequently . This qualification separates initialization from the usual amortized analysis starting at zero.
Eliminating the phase velocity from the first two relations yields
With , put
Then . The dispersion relation becomes
Here follows from . The parameter has dimensions of length; and are dimensionless.
For the strict mode count for a rigid-backed elastic layer, consider
The right side is negative, so intersections occur only on the negative branches of the tangent,
On each such branch is strictly increasing. If , its limit at is negative infinity. At the other end of the available interval, it is positive: either with , or with . The intermediate value theorem and strict monotonicity give exactly one intersection. No such interval exists when .
Figure 1.
Intersections of the negative tangent branches with the interface loading curve. A branch beginning exactly at the cutoff contributes no trapped mode.
Details.
Thus the exact answer, including all cutoff values, is
Away from , this equals the printed floor function expression . At , the printed expression is one too large: the th interval is empty and the limiting state has , contradicting exponential decay. This exception is present in the native paper, rather than introduced by transcription.
Now hold fixed and let . Neglecting the right side gives and hence the candidate phase velocities
The zero is excluded: it would require , already ruled out. For every , the candidate is a valid leading asymptotic expansion. A first correction, obtained by expanding the tangent about , is
The big O notation here assumes a fixed positive gap between and . In particular, when , all leading approximations are valid. The phase velocity increases strictly with , so only the last branch can cause an endpoint difficulty.
If , the formal last equation root lies outside the allowed interval. The actual last equation root approaches , where the small factor is balanced by the vanishing denominator. This is a singular perturbation. For fixed strictly inside that interval, write . Since ,
The valid endpoint approximation for a rigid-backed shear mode consequently gives
Here we used and . Thus this normal mode approaches the upper wave speed from below; it does not approach the inadmissible value obtained from .
There is a further exceptional fixed value . Put again. Now , so the balance changes to
In the last formula the bracket specifies the first nonzero correction. The zeroth-order candidate is correct as a limit but misses this correction and the positive exterior exponential decay rate. More generally, close to , let and . For , a transition approximation valid on both sides is
It recovers the balance at and the ordinary expansion above the transition. The fixed-endpoint formula involving should be used when is below, and bounded away from, .
For each , let . The floor function ensures , even when the quantity being rounded is negative. The integer endpoint hypothesis gives . Thus the error of the rounded Bernstein polynomial satisfies
It suffices to bound this unnormalized sum uniformly. If , put and sum a geometric series:
The last inequality follows by maximizing , whose maximum occurs at and is at most . Reflection gives the same bound for . In the middle interval both and are at most , so each summand is at most . Therefore, for ,
Endpoint integrality matters: at zero or one a noninteger value would leave a fixed nonzero rounding error.
The floor function has even value on indices congruent to zero or one modulo four, and odd value on indices congruent to two or three. Accordingly the displayed sequence has terms in the first two residue classes and in the other two. In particular,
Every term is within of the set . If a subsequence converged to , its eventual distance from that set would be bounded below by a positive constant, contradicting this bound. The complete set of subsequential limits is .
The integer endpoint hypothesis is important. Let . The floor function gives , while because and are integers. Therefore the rounded Bernstein polynomial satisfies
For , the successive terms have ratio , so the geometric series estimate gives
The last inequality follows by maximizing at . The same bound holds on by reflection. On , each factor and is at most , giving . Thus
Here ; for the difference vanishes. Without the integer endpoint hypothesis the claim would fail: at the error is , independently of .
Let and use the floor function to choose
Interpret an empty integer interval as an empty sum. These bounds give exactly the event , where has the binomial distribution of parameters . Since , the central limit theorem for a sum of independent Bernoulli distribution variables gives convergence in distribution of that standardized count to the standard normal distribution. Its cumulative distribution function is continuous at both endpoints, so
The TeX's additional malformed inequality involving and is absent from the PDF and is not a condition on the requested integers.
Use the cyclic logarithmic coloring
Here the floor function places in the unique half-open real interval . If , then
because . For any real and , is either or . Applying this to the logarithms of and shows that their bin indices differ by or , and hence have different residues in modular arithmetic modulo . This proves the required separation, including both endpoints of the prescribed ratio interval. The half-open bins remove any ambiguity at their boundaries.
Fix a number of colors. For a two-point set whose points are distance apart, take the vertices of a regular simplex with vertices and side length . The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.
For an equilateral triangle of side length , take a regular simplex with vertices and side length . The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.
To prove the product theorem for Euclidean Ramsey sets, let be a finite Ramsey witness for under colors. There are at most possible color patterns on . Choose a finite Ramsey witness for under that many colors. Given a -coloring of , color each by the complete pattern
There is a copy on which this pattern is constant. The common pattern on contains a monochromatic copy . Every point of then has the same original color, and the orthogonal product is congruent to .
A rectangle is the Cartesian product of two line segments, so it is Euclidean Ramsey. Three suitable vertices of a rectangle form a right triangle; any subset of a monochromatic set is monochromatic. Thus every right triangle is Euclidean Ramsey.
It remains to show that the collinear set behaves differently. In every , use the finite coloring
A congruent copy has the form with for the Euclidean norm. The parallelogram law gives
Put , , and . The errors introduced by the three floor functions show that
If all three points had one color, the integer in the middle would be divisible by ten, which is impossible. This proves the three-term unit arithmetic progression is not Euclidean Ramsey assertion.
Write the Chebyshev theta function as
Taking natural logarithms in part a gives
and hence
Because , the right-hand side is at least for every sufficiently large integer .
Now let be sufficiently large and set using the floor function. Then and , so the monotonicity of gives
All three examples below have positive integer coefficients, so they work under either convention for whether .
For , take . This is the geometric series: it converges for , and its terms fail to tend to zero for .
For , take , using the factorial and . For every fixed , the absolute values of successive terms have ratio . This eventually exceeds two, so the terms grow without bound and the series cannot converge. At it is finite, giving radius of convergence zero.
For , take
using the floor function. The coefficients satisfy
The upper bound and the comparison test for series give absolute convergence when . The lower bound prevents the terms tending to zero when . Hence the radius of convergence is exactly .
The Bolzano-Weierstrass theorem states that every bounded sequence of real numbers has a convergent subsequence. It is enough to select infinitely many terms of the tangent sequence that stay uniformly bounded.
For each positive integer , choose , using the floor function. Then . Moreover , so these are strictly increasing indices. By the period and monotonicity of the tangent on ,
Thus is a bounded subsequence. Applying the Bolzano-Weierstrass theorem to it gives a convergent subsequence, which is also a subsequence of the original sequence. Such a convergent subsequence therefore exists.
Every is a Borel measurable function of , by the formula involving the floor function. Thus
Conversely, part (i) gives the everywhere identity . For fixed , this is the pointwise limit of random variables measurable with respect to . Such a limit of a sequence is measurable, so . Consequently
These are increasing-precision observations even when the first finitely many are discarded; they do not behave like the independent random variables whose tail sigma-algebra appears in Question 1(b).
The floor function gives the deterministic bound
for every outcome, including . Thus all three convergence assertions hold: there is pointwise, and hence almost sure convergence, as well as convergence in probability and convergence in L2. In detail, for the probability is zero as soon as ; also
The uniform distribution even gives the exact second moment of the error by integrating over the dyadic partition:
For , repeated use of the floor function identity gives
Thus the filtration satisfies . Each positive-probability atom of a sigma-algebra here has the form
with probability ; is a possible additional null set atom. Averaging over each dyadic interval gives a version
For a globally defined version of the right side, assign any value, for example zero, on .
Indeed, the displayed random variable is -measurable and bounded by . On each its integral is
by the uniform distribution. Every member of is a union of the displayed sets and the possible zero-probability atom. Summing these identities therefore verifies the defining conditional expectation property on all of .
Put . Because , is a nonnegative integer, and
The function is strictly increasing for , so . Both powers are integers. Taking the floor function therefore gives
Taking nonnegative th roots now gives . Consequently
The argument also covers , when both outer floors are zero.