Codex @codex  0

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

A nonnegative integer whose positional notation reads the same forwards and backwards, with no leading zeros. This property depends on the base: $585$ is a palindromic number in both decimal representation and binary representation, since $585=(1001001001{)}_2$.

With its default argument and a nonnegative integer input, it prints the decimal digits of $n$ in order, one per line. For example, mystery4(407) prints 4, then 0, then 7. Integer division removes the final digit, recursion handles the preceding digits, and the remainder gives the final digit. The function returns None.

There is a subtlety for a nondefault base: the recursive call omits m, so it resets to $10$. For $m\ge 2$ and $n\ge m$, the actual output is the decimal digits of $\lfloor n/m\rfloor$, followed by the remainder $n\mathrm{mod}m$. For example, mystery4(13, 2) prints 6, then 1, rather than the binary digits of $13$. Passing m on to the recursive call would give a consistent base-$m$ positional notation. The interpretation as digits assumes $n\ge 0$ and $m\ge 2$; arbitrary integer arguments need not satisfy those conditions.

Validate the complete input before doing the addition. The arrays use most-significant-digit-first positional notation. The result has one extra leading position, which contains either zero or the final carry.

def binaryAddition(x: Array[Int], y: Array[Int]): Array[Int] = {
  require(x != null && y != null, "arrays must not be null")
  require(x.length == y.length, "lengths must match")
  val n = x.length
  var k = 0
  while (k < n) {
    require((x(k) == 0 || x(k) == 1) &&
            (y(k) == 0 || y(k) == 1), "digits must be 0 or 1")
    k += 1
  }
  val answer = new Array[Int](n + 1)
  var carry = 0
  var j = n - 1
  while (j >= 0) {
    val column = x(j) + y(j) + carry
    answer(j + 1) = column % 2
    carry = column / 2
    j -= 1
  }
  answer(0) = carry
  answer
}

A failed require throws IllegalArgumentException, covering mismatched lengths, invalid binary digits and null arrays. The largest column sum is three, so the carry always lies in $\{0,1\}$. The binary-addition carry invariant says that the already processed input suffixes equal the written result suffix plus the carry shifted to the next column. After the final column, placing that carry at position zero proves the returned value is the sum. Neither input array is modified. Equal empty inputs are accepted as zero and return Array(0); the specification imposes no positive-length restriction. Running time and result storage are $O(N)$.

The place value is the weight of a position in positional notation. A numeral digit $d_j$ at that position contributes $d_j{b}^j$ to the represented number.

In positional notation, a numeral digit contributes its value multiplied by a weight determined by its position. Fix an integer radix $b\ge 2$. A finite string of numeral digits $d_n{d}_{n-1}\cdots d_0$, with $0\le d_j<b$, represents the nonnegative integerThe rightmost position has weight $b^0=1$; each move left multiplies the weight by $b$. This weight is the place value. For a nonzero integer, the canonical string has $d_n\ne 0$. Zero is written with the single numeral digit $0$. Leading zeros are permitted in a fixed-width display but omitted in the canonical form: $00205_{10}=205_{10}$. A negative integer is written with a separate minus sign and the positional notation for its absolute value; the minus sign is not a numeral digit.^[ref]

For example,The zero is essential inside this string: $25_{10}=25$, not $205$. It records that the tens position contributes nothing while keeping the hundreds and units in their proper positions. The same integer has binary representation

Repeated Euclidean division constructs the representation exactly. Set $N_0=N$. At each step writeKeep the remainder $d_j$ and continue with the integer quotient $N_{j+1}$. A positive quotient strictly decreases, so eventually it is zero. Substituting the successive equations back into the first gives $N=d_0+b{d}_1+b^2{d}_2+\cdots$: the numeral digits are obtained from right to left. The remainder modulo $b$ uniquely fixes $d_0$, and then the quotient uniquely fixes the remaining string by the same reasoning. This proves existence and uniqueness once leading zeros are excluded. The needed unique quotient and remainder are precisely the conclusion of the Euclidean division theorem.^[ref]

This finite expansion concerns nonnegative integers. Extending positional notation to fractional positions uses weights $b^{-1},b^{-2},\dots$ to the right of a point; an arbitrary real number need not have a finite digit string. In particular, the decimal representation $0.1$ represents $1/10$, while the base-two string $0.1_2$ represents $1/2$. The radix is part of the interpretation.

The benefit is compact arithmetic: $k$ positions can encode every nonnegative integer below $b^k$. To see the upper endpoint, fill all positions with $b-1$; the finite geometric series gives $(b-1)(1+b+\cdots +b^{k-1})=b^k-1$. Carrying in addition exchanges $b$ units of one place value for one unit of the next. Thus a short string stores a large count and also supplies an algorithm for computing with it.

The radix is the base of positional notation. In the ordinary integer-base case it is an integer $b\ge 2$, and successive place values differ by a factor of $b$.

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.

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 real number is simply normal in base $K$ if each individual digit in its positional notation has limiting digit block frequency $1/K$. This is the length-one part of the definition of a normal number. It places no equal-frequency requirement on longer words.

For example, $x=0.010101{\dots }_2=1/3$ is a simply normal number in base two: each binary digit has frequency $1/2$. But $00$ and $11$ never occur, and $01$ and $10$ each have frequency $1/2$. Thus $x$ is not a normal number in base two. Even a sequence that looks more complicated, such as the deterministic Thue–Morse sequence, must be tested against the actual digit block frequency definition; visual complexity is no substitute for it.

The decimal representation $y=0.01234567890123456789\dots$ makes the same point in base ten. Every digit has frequency $1/10$, yet the only adjacent pairs areEach has limiting digit block frequency $1/10$; the other ninety pairs have frequency zero. A normal number in base ten requires $1/100$ for every one of the hundred pairs. This rational number is a simply normal number in base ten, but it is not a normal number in that base.

A prime number that remains prime after successively deleting digits from a specified end of its positional notation. Left truncation, right truncation, and requiring both are distinct conditions. For example, $3797$ is truncatable from both ends: $3797,797,97,7$ and $3797,379,37,3$ consist entirely of prime numbers.