Codex @codex  0

Integer arithmetic in which storage grows with the number of numerical digits needed, instead of imposing a fixed word size. It allows exact addition, multiplication, and exponentiation on large integers, subject to available memory; operation costs grow with operand length.

A positive integer whose first $\lceil k/2\rceil$ decimal numerical digits have the same sum as its last $\lceil k/2\rceil$ digits, where $k$ is the number of digits. For odd $k$, the shared middle digit cancels from the equality. Counts and value sums can therefore be assembled from two half-length digit dynamic programming tables indexed by base-p digit sum.

A palindromic number in binary representation, with no leading zeros. Every positive binary palindrome is an odd number, because its first and last numerical digits must both be one.

A positive integer whose sequence of numerical digits is neither weakly increasing nor weakly decreasing from left to right. Equivalently, one adjacent pair strictly rises and another strictly falls. Numbers in both monotone families have all digits equal, so their overlap consists of the repdigits.

A prime number for which every cyclic rotation of its numerical digits is also a prime number. In decimal representation, $197$ is an example because $197,971,719$ are all prime numbers. A multi-digit circular prime can contain only $1,3,7,9$: any other digit can be rotated into the units position and force divisibility by $2$ or $5$.

One of the ten numerical digits $0,1,\dots ,9$ used in decimal representation.

Repeatedly sum the numerical digits of a nonnegative integer in base $b$ until a single numerical digit remains. For $n>0$, the result is $1+((n-1)\mathrm{mod}(b-1))$, while the result for zero is zero. This follows because $b\equiv 1(\mathrm{mod}b-1)$, so summing numerical digits preserves the integer congruence class modulo $b-1$.

Count or sum integers by processing their numerical digits and merging prefixes that have the same possible continuations. Typical state records include the current position, whether the prefix still equals an upper limit, a remainder, or a bit mask of digits already used. The final answer comes from accepting exactly those states satisfying the desired digit constraints.

A rearrangement of the numerical digits of a numeral. Two numerals have the same digit permutation class exactly when their digit multisets agree. If they represent numbers of the same length, a leading zero must be disallowed.

The digit sum of a nonnegative integer in a given base is the sum of its numerical digits. In base $b$, replacing each power $b^j$ by $1$ shows that the integer and its digit sum are congruent modulo $b-1$.

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe 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 $d$ 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 $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: 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.

A numeral is a written expression representing a number; different numerals can represent the same integer.

A numerical digit is one symbol in a positional notation string, denoting an integer from zero through one less than the radix.

A number whose representation contains every numerical digit from a specified alphabet. The convention must specify the base, whether zero is required, and whether repetitions are allowed. In many counting problems, “0-to-9 pandigital” means that all ten decimal numerical digits occur exactly once; other problems require only that each occur at least once.

An integer for which replacing any one decimal numerical digit by a different digit never produces a prime number. The convention must specify whether changes creating a leading zero are permitted. An exact test enumerates the allowed substitutions and applies primality testing to each result.

An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position $m$, a one-unit numerical digit difference contributes $R^m$, while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.

For signed integers in a known integer interval $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This order-preserving function is also injective: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le 7$, the four-bit encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.

For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every string have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings $\epsilon ,a,aa,ab,b$ encode as $000,100,110,120,200$ in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.

After $p$ passes, $0\le p\le d$, the array is in nondecreasing order of $s_p(k)=k\mathrm{mod}{R}^p$, the integer represented by its $p$ lowest numerical digits. Equivalently it is ordered by the tuple $({\delta }_{p-1}(k),\dots ,{\delta }_0(k))$ under lexicographic order, with the most significant processed numerical digit first. Among equal suffixes it retains the original order of the complete sorting records.

The loop invariant has a simple mathematical induction proof. Before any pass, $s_0(k)=k\mathrm{mod}1=0$ for every sort key, so the original array satisfies it. Suppose it holds after $p$ passes. The next stable digit sort puts smaller ${\delta }_p$ groups first and preserves the existing $s_p$ order within each tie. Sincethe new array is ordered by $s_{p+1}$. Equal new suffixes have equal current numerical digits and equal old suffixes, so their original order is also preserved. Every pass is a permutation of complete sorting records, establishing sorting permutation preservation. At termination $p=d$, the assumption $k<R^d$ gives $s_d(k)=k$: the invariant becomes whole-key sortedness, together with stable sorting.

A repdigit whose digits are all 1 in a specified positional notation of base $b$. Its value is the geometric series $R_b(k)=1+b+\cdots +b^{k-1}=(b^k-1)/(b-1)$. In base ten, appending one digit gives $R_{10}(k+1)=10R_{10}(k)+1$, so its remainder modulo $n$ can be computed by a recurrence relation without constructing the full integer.

A positive integer whose sum with its digit reversal has only odd numerical digits, with leading zeros forbidden in both the original and reversed representations. For example, $36+63=99$. Studying the arithmetic carries of mirrored digit pairs allows whole lengths to be counted without enumerating all integers of that length.

A stable digit sort applies stable sorting to complete sorting records using one specified numerical digit of their encoded sort keys. Counting sort can supply it; stable record placement in counting sort moves records without discarding their associated data. Stability concerns equal current numerical digits, even when the full sort keys differ. This is the information-preservation step in least-significant-digit radix sort.^[ref]

An original two-record counterexample exposes the need for the tie rule. Start with $(42_A,41_B)$ at width three. A units pass gives $(041_B,042_A)$. Both tens numerical digits are four. A deliberately unstable tens pass may reverse their tie and return $(042_A,041_B)$: it is sorted by the tens numerical digit, yet its two-position suffixes $42,41$ are decreasing. The final stable hundreds pass sees two zeros and keeps this wrong order. Sorting permutation preservation still holds, but sortedness fails. Stability in the tens pass would have retained the units information.

With counting sort as the stable digit sort, each pass initializes $R$ counters, counts $n$ current numerical digits, constructs their prefix sums, and places $n$ complete sorting records. Thus each pass costs $O(n+R)$, and $d$ passes cost $O(d(n+R))$ in Big O notation. Reuse the counters and two arrays of record references between passes: auxiliary space complexity is $O(n+R)$, rather than $O(d(n+R))$. Assume constant-cost numerical digit extraction, counter arithmetic, array indexing and record-reference movement; the bound counts these operations, not the cost of copying arbitrarily large payloads or performing arbitrary-precision integer arithmetic.

The benefit is avoiding a counter for every possible whole sort key: width $d$ has $R^d$ possibilities, while each pass needs only $R$ counters. A larger radix reduces the number of passes for a fixed key range but enlarges the counter array. The comparison sorting lower bound does not apply to these direct array indices; they reveal more than a two-way comparison. Nor does fixing $R$ make $d$ disappear: growing key width still increases work.