""" dual.py -- the leading end of base b: what a reader of an integer's sign, exponent and first t digits computes, and how it mirrors the trailing end. QUESTION. Base b writes a positive integer n with e + 1 digits, e = floor(log_b n). The LEADING numeration reads it top first: its depth-t TILE is the set of integers with the same digit count and the same t leading digits, so the archimedean window, size, read to t digits. The trailing numeration reads the same integer bottom first, and its depth-t tile is n mod b^t. A map f of the positive integers is READ AT LOOKAHEAD c when, at every depth t, the depth-t tile of f(n) is a function of the depth-(t + c) tile of n, over the n with f(n) >= 1 (zero has no leading tile). Which places does each end read and hide, which operations does the leading end read, at what least lookahead, and what does it read that no arithmetic map is? THE ARGUMENT (written before this script). (1) THE TILE LEMMA. If e + 1 <= t the depth-t tile of n is {n}. Otherwise it is [P b^j, (P + 1) b^j) with j = e + 1 - t, P the t-digit prefix: b^j consecutive integers. The tile is DEEP when j >= 1. So a deep tile of span j is a complete residue system mod b^j, and n mod m (m >= 2) is constant on no tile of length >= 2. The predicate [m | n] can still be: a tile shorter than m holding no multiple of m decides it false. At base 2, [4, 6) is the depth-2 tile of 4 and 5 and decides [7 | n]. (2) THE TWO-ENDS LAW. For m >= 2 and j >= 0: n mod m is a function of the last j digits iff m | b^j, and every residue mod m has the same count on every span-j leading tile iff m | b^j. The first is the suffix read. For the second, a span-j tile is b^j consecutive integers: each residue appears b^j/m times when m | b^j, and otherwise floor(b^j/m) or floor(b^j/m) + 1 times, both counts occurring, on every such tile. So one condition decides both ends: depth j at the trailing end reads m exactly where span j at the leading end hides it exactly. A prime p is read by some trailing depth, and hidden on every deep leading tile, iff p | b. A prime not dividing b is read at neither end. (3) THE CROWN EXCHANGE. b^(e(x) + e(y)) <= xy < b^(e(x) + e(y) + 2), so e(xy) - e(x) - e(y) is 0 or 1: a product's exponent is read from the factors' to one bit. A difference's is not. Two points of one deep tile of span j differ by any integer in (-b^j, b^j), so their difference takes every exponent 0..j - 1, both signs, and 0. Hence [x = y], the sign of x - y and e(x - y) are functions of no pair of depth-t tiles once one is deep: equality and near comparison are walled at every depth, while sign and exponent are native. A residue ring reads x - y = 0 exactly, channel by channel, and on a squarefree modulus the ring's support log reaches 0 by a drop to a smaller support. The leading read is a chart of the real logarithm that omits 0, and a difference is the operation that reaches it. Both logarithms are singular at 0; a squarefree residue ring reads through that point, the leading end is walled by it, and the trailing end of Z reads x = y only modulo b^t. (4) THE COSET RIGIDITY. Let a digit set D represent every integer as a finite trailing string, as {-a, ..., a} with 2a + 1 >= b and a >= 1 does: take d = n mod b in D, n' = (n - d)/b, so |n'| <= (|n| + a)/b < |n| while |n| > a/(b - 1), and a/(b - 1) <= a is a digit. Then the completions of a trailing prefix of value V and length t are exactly V + b^t Z, since the extension's digits write any integer z and nothing else. Two such tiles are equal or disjoint, so the tiles are the b-adic balls however redundant D is, and the trailing Lipschitz and division criteria hold unchanged: no digit set buys the trailing end an overlap. (5) THE AFFINE CLASS THEOREM. Let f be nondecreasing with |f(n) - lambda n| <= C, lambda > 0, and Delta = ceil(C/lambda) + 1. f is read at some lookahead iff (SLOPE) lambda = b^r/h for integers r >= 0, h >= 1, and (ALIGNMENT) for some K >= 0 every positive multiple N of h b^K has f(N) >= lambda N > f(N - 1). The crossing of B is n*(B) = min{n : f(n) >= B}, and |n*(B) - B/lambda| <= Delta. The depth-t output boundaries are the integers M b^J with 1 <= M < b^t; for monotone f a depth-(t + c) input tile maps into one depth-t output tile iff no boundary's crossing sits strictly inside it, so f is read at lookahead c iff every crossing n* with f(n* - 1) >= 1 lying in a deep tile of span j = digits(n*) - t - c is its left end, b^j | n*. SLOPE. n*(b^J) has at least J - G digits for a constant G, so its depth-(1 + c) tile has span at least J - G - 1 - c, and b^(J - G - 1 - c) divides it. The integer n*(b^J)/b^(J - G - 1 - c) lies within Delta b^(G + 1 + c - J) of the fixed real b^(G + 1 + c)/lambda, which is therefore an integer: lambda is a power of b over an integer, b^r/h once r is taken least. ALIGNMENT, necessity. For J >= r, N0 = M b^J / lambda = h M b^(J - r) is an integer and the crossing lies within Delta of it, with at least t + J - r - 1 digits, so alignment gives b^(J - r - 1 - c) | n*. N0 is a multiple of the same power, and once b^(J - r - 1 - c) > Delta the two coincide. The threshold J0 depends on neither M nor t, so every multiple of h b^(J0 - r) is its own crossing. ALIGNMENT, sufficiency. For J >= r + K the crossing of M b^J is N = h M b^(J - r), with at most digits(h) + t + J - r digits, so at c >= digits(h) its tile has depth at most J - r and N is aligned. For J < r + K the crossing is below h b^(t + K - 1) + Delta + 1, so it is shallow at c >= digits(h) + K + digits(Delta). COROLLARIES. floor((u/v) n) with gcd(u, v) = 1 has lambda = u/v: the slope needs rad(u) | rad(b), and then h = v b^r / u, every multiple N of h has f(N) = lambda N > f(N - 1), and K = 0. So it is read iff rad(u) | rad(b), THE NUMERATOR CRITERION, the denominator free. floor((n + s)/v) with 0 < s < v has f(N - 1) = N/v at every multiple of v, so it fails at every K: read iff s = 0. n + omega is read iff omega = 0. THE SUM CRITERION: f = sum w_i floor(n/v_i), w_i >= 1, l = lcm(v_i), U = sum w_i l/v_i, lambda = U/l. f(n) <= lambda n with equality iff l | n, and f(N - 1) = lambda N - sum w_i when l | N, so the alignment condition holds at K iff l | h b^K iff U | b^(r + K): f is read iff rad(U) | rad(b), with U the numerator over the lcm, unreduced. At (3, 7), base 10, U = 10 and f is read; at (3, 6) U = 3 and lambda = 1/2, so the slope holds and alignment fails at every base prime to 3. g = floor(n/3) + floor(n/7) is no floor((10n + s)/21), which stays within 1 of 10n/21, since g(20) - 200/21 = -32/21. (6) THE LEAST LOOKAHEAD. With h as in (5), K least, delta = digits_b(h), mu = v_b(h) and h' = h/b^mu: THE DEEP BOUND. For J >= r + K the crossing of M b^J is N = h M b^(J - r), its depth-(t + c) tile has depth digits(hM) + J - r - t - c, and N is aligned iff c >= D(M) = digits(hM) - t - v_b(hM). For M prime to b, v_b(hM) = mu, so D(M) = delta - mu = digits(h') when the product OVERFLOWS into delta + t digits, and delta - mu - 1 otherwise. (v_b is not additive at composite b, 2 * 5 at base 10, which is why M is taken prime to b.) The overflow interval [b^(delta + t - 1)/h, b^t) is nonempty iff h > b^(delta - 1), that is iff h' >= 2, its length grows with t, and b consecutive integers hold one = 1 mod b. So c_min >= c_deep = digits_b(h') - [h' = 1], a deep misaligned crossing at c_deep - 1 at every large J; and every D(M) <= c_deep. THE SHALLOW LAYER. For J < r + K the crossing is below b^(delta + t + K - 1) + Delta, so below b^(delta + t + K) when Delta <= (b - 1) b^(delta + K), and its tile has depth at most delta + K - c. So c_min <= max(c_deep, delta + K) under that condition. THE LEAST-LOOKAHEAD LAW. When K = 0, b does not divide h, h >= 2 and Delta <= (b - 1) b^delta: c_min = digits_b(h). c_scan, the largest lookahead any crossing the script scans needs (PK), is at most c_min. The script counts the cells with c_scan <= max(c_deep, delta + K - 1), which is no bound on c_min. (7) THE STRUCTURAL SPLIT. A map is read at lookahead 0 iff it sends every tile into a tile of the same depth, and nothing there asks for arithmetic. At base 2, x(n) = n XOR 2^(e - 1) (e >= 1) flips the second digit; at base 10, pi(n) applies the digit permutation d -> 9 - d to the second digit; P(n) = b^e is monotone with P(n)/n running over (1/b, 1], so no line is within a bounded distance of it. All three are read at lookahead 0, and x and pi are not monotone. On a finite product of finite fields a map is channel-local iff it is a polynomial (the locality criterion), so on a squarefree residue ring locality and algebra coincide; the trailing end of Z, Z/b^t with t >= 2, is no such ring. At the leading end they part. (8) THE REDUNDANT READER (written before its engine). Give the leading end the digits {-a, ..., a}, 2a + 1 > b, and read a string 0.d_1 d_2 ... as y = sum d_i b^-i in [-rho, rho], rho = a/(b - 1) > 1/2. (i) The completions of a depth-t prefix of value V are exactly the closed interval T = [V - rho b^-t, V + rho b^-t]: the j-digit strings write every integer in [-a R_j, a R_j], R_j = (b^j - 1)/(b - 1), by induction (the intervals [bz - a, bz + a] over consecutive z abut since 2a + 1 >= b), and a limit of finite completions is a completion. (ii) T's children are [V + d b^-(t+1) - rho b^-(t+1), V + d b^-(t+1) + rho b^-(t+1)], d = -a..a; the extreme ones reach V +- (a + rho) b^-(t+1) = V +- rho b^-t, so they cover T, and adjacent ones overlap by (2 rho - 1) b^-(t+1) > 0. So every subinterval of T of length at most (2 rho - 1) b^-(t+1) lies in one child: the purchase is a positive Lebesgue number. (iii) Let F map [-rho, rho]^k to [-rho, rho], L-Lipschitz in the sup metric. At lookahead c with b^c >= 2 rho L / (2 rho - 1), if the depth-t output tile holds F of the input's depth-(t + c) tiles, as [-rho, rho] does at t = 0, then F of the depth-(t + 1 + c) tiles lies inside it with diameter at most 2 rho L b^-(t+1+c) <= (2 rho - 1) b^-(t+1), so it fits a child; committing that child keeps the hypothesis. So F is read at lookahead max(0, ceil(log_b L + log_b(2a/(2a - b + 1)))). At (2, 1) this is max(0, ceil(log_2 L) + 1). A scaling y -> (u/v) y with |u/v| <= 1, the mean (x + y)/2 and the product xy/rho are Lipschitz, so the leading end's walls on them dissolve; the order reads do not. (9) THE HEDGE. If moreover a <= b - 1, so rho <= 1, the first nonzero digit d_i of a prefix fixes the sign of every completion: |V| - rho b^-t >= b^-i (1 - rho) >= 0. So the reader that copies the prefix, negated when its first nonzero digit is negative, keeps each output tile equal to |T|: y -> |y| is read at lookahead 0. Sign is read at no depth: the all-zero prefix's tile holds both signs at every depth. At a > b - 1 the first nonzero digit no longer fixes the sign: at (2, 2), 0.1 followed by -2's reaches 1/2 - 2 * 1/2 = -1/2. (10) WHAT THE PURCHASE SPENDS. (a) THE ORDER BLUR. Two depth-t tiles of values V < V' have completions in both orders iff their interiors meet, iff V' - V < 2 rho b^-t; the prefixes are b^-t apart at least, so a tile's order is open against the 2K neighbours with K = ceil(2a/(b - 1)) - 1, 2K + 1 tiles in all, three at (2, 1) and (10, 6), one at a non-redundant end. (b) NO NORMALIZATION. The tile of 1 0 ... 0 (t digits) is [1/b - rho b^-t, 1/b + rho b^-t], which holds 1/b in its interior at every depth, so neither the exponent of y nor its standard string is read there. (c) THE LEAK. Read an integer with t + j signed digits: a prefix of value V has the completions V b^j + z, each z in [-a R_j, a R_j] once as a value and N_j(z) times as a string. For p | b, R_j = 1 mod p and z = d_0 mod p, where d_0 is the last digit. So under counting the residues mod p are uniform on the completions iff p | 2a R_j + 1 iff p | 2a + 1, with bias below 1/(2a R_j + 1), and under the string measure iff p | 2a + 1, with a bias independent of j. The non-redundant end hides p exactly (the two-ends law); redundancy leaks it unless p | 2a + 1. This spends a finite place's hiding, not archimedean data. (d) DIVISION'S BIT. y -> x/y is read at no depth on a y-prefix of zeros, whose tile holds values of both signs arbitrarily near 0, so the quotient's image is unbounded. Given |y| >= D, D x/y is (1 + 1/D)-Lipschitz on [-rho, rho] x {D <= |y| <= rho} at rho = 1 and (8) reads it: the one bit of size the reader cannot make. (11) THE PERIOD LAW. Non-redundant digits, multiplier a >= 2, alpha = floor(log_b a). An input tile [P b^j, (P + 1) b^j) at depth t' = t + l, of span j, maps into a * [P b^j, (P + 1) b^j - 1]; with theta = [a P >= b^(t' + alpha)] the image's depth-t output tiles have length b^J, J = j + Lam, Lam = l + alpha + theta. The tile is an EXCEPTION iff a multiple of b^J lies in (a P b^j, a P b^j + a (b^j - 1)], iff 1 <= s <= a (b^j - 1)/b^j with s = (-a P) mod b^Lam (s = 0 fails, as b^Lam > a). Over b^Lam consecutive P of one class, s runs over the multiples of d = gcd(a, b^Lam), each d times, so the count of exceptions is exactly d * floor(a (b^j - 1)/(b^j d)), a - d when b^j d > a. It is 0 iff d > a (1 - b^-j), and since d | a and 1 - b^-j >= 1/2, iff d = a: iff rad(a) | rad(b) and Lam >= max_p ceil(v_p(a)/v_p(b)), the numerator criterion's multiplier half at its depth threshold. THE COUNTING COLLAPSE: for a prime to b on deep tiles (b^j > a) the count is a - 1 per b^Lam, and the two classes hold the fractions w0 = (b^(alpha+1) - a)/(a (b - 1)) and 1 - w0 of the t'-digit P as t' grows, so the density of exceptions tends to (a - 1) b^-(l + alpha) (w0 + (1 - w0)/b) = (1 - 1/a)/b^l, the base and the multiplier's size gone. THE HUMP: weighting each tile by log_b((P + 1)/P), the class fractions are 1 - xi and xi, xi = {log_b a}, and the density tends to (1 - 1/a) H(xi)/b^l, H(xi) = b^(xi-1) (1 + (b - 1)(1 - xi)); ln H is concave and 0 at xi = 0 and 1, so H > 1 inside. (12) THE DUAL HAAR. The mantissas form the compact group R_>0/b^Z, whose Haar measure is log-uniform, and the mantissas of the depth-t leading tiles with prefix P lie in the arc [P, P + 1) b^Z, of Haar log_b((P + 1)/P), Benford's law. The arcs have unequal Haar, which is why a density at the leading end names its measure; residue classes are cosets of equal Haar, which is why none at the trailing end needs to. An arc's Haar is invariant under multiplication by every q > 0 because log is a homomorphism; counting is not. HAND-ATTACK (on paper, before any engine code). - Crossings of g = floor(n/3) + floor(n/7) at base 10: l = 21, U = 10, lambda = 10/21, r = 1, h = 21. n*(M 10^J) = 21 M 10^(J - 1) for J >= 1. At t = 1, M = 5, J = 1: n* = 105, three digits, depth at lookahead 1 is 3 - 1 - 1 = 1, and 10 | 105 fails: a witness at c = 1. At c = 2 the depth is 0. delta = 2, h' = 21, c_deep = 2, K = 0, Delta = ceil((32/21)/(10/21)) + 1 = 5 <= 9 * 100, so the law gives c_min = 2. - floor(n/3) at base 10: h = 3, delta = 1, law c_min = 1. floor(2n) at base 2: lambda = 2 = 2/1, h = 1, h' = 1, c_deep = 0; the shallow layer J < r = 1 has crossing ceil(M/2), fewer digits than M, depth at most 0 at c = 0; c_min = 0. - floor(n/9) at base 2: h = 9, delta = 4, h' = 9, c_deep = 4; overflow needs 9M >= 2^(t + 3) with M odd and t-digit: t = 1 (M = 1) gives 9 < 16; t = 2 (M = 3) 27 < 32; t = 3 (M = 5, 7): 45, 63 < 64; t = 4, M = 15: 135 >= 128. So the deep witness at c = 3 first appears at t = 4. - The digit count of the crossing in (5)'s necessity: N0 >= b^(t - 1 + J - r) and N0 - Delta can lose one digit, hence t + J - r - 1. - (3) at base 2, span 6: the tile [64, 128) holds pairs at every difference -63..63, exponents 0..5. PREDICTIONS (frozen before any engine code). C0 CONTROLS, read first. The brute tile reader (every n below b^E, grouped by input tile, outputs compared by tile) finds floor(2n) read at c = 0 and floor(3n) at no c <= 3 at base 2, and floor(n/3) read at c = 1 but not 0 and floor((n + 1)/3) at no c <= 3 at base 10, at depths t = 1..3. The crossing reader returns the same verdicts, and agrees with the brute reader at every sum cell below at depths 1 and 2 and c <= 3 over the brute range. Kill: any disagreement. PT The leading-tile lemma: every depth-t tile of n below b^E, t = 1..4, at bases 2, 3 and 10 is an interval of the stated length. [4, 6) is a depth-2 tile at base 2 holding no multiple of 7. No deep tile in range decides n mod m for m = 2..12. Kill: one tile off. PH The two-ends law at bases 2..12, m = 2..30, j = 0..4: uniform residue counts on every span-j tile with prefix of 1 or 2 digits iff m | b^j, and n mod m a function of the last j digits over n < b^(j + 3) iff m | b^j. Kill: one (b, m, j) where the three disagree. PZ The crown exchange: e(xy) - e(x) - e(y) in {0, 1} for every x, y below 2^10 at base 2, 3^7 at base 3 and 500 at base 10; the differences within the depth-6 tile [64, 128) at base 2 and the depth-3 tile [1000, 2000) at base 10 realize every exponent below the depth, both signs, and 0. Kill: a third value or a missing one. PC The coset rigidity at (b, a) = (2, 1), (3, 1), (4, 2), (10, 5), (10, 6): the digit recursion writes every |n| <= 10^4 and reads it back; for every trailing prefix of length t <= 3, the values of its extensions by s = 5 more digits contain every point of V + b^t Z within b^(t + 3) of V and nothing off it. Kill: one point missed or one off the coset. PA The affine class, at the 171 cells of 55 pairs 2 <= v1 < v2 <= 12 at bases 2, 6, 10 and six weighted sums at base 10 ((2, 3)(1, 7), (3, 3)(1, 7), (2, 3)(2, 7), (1, 2)(1, 5)(1, 10), (1, 2)(1, 3)(1, 7), (1, 3)(1, 7)(1, 21) as (w, v)): the crossing reader (least c <= 10 with no misaligned deep crossing at t = 1..3 and J <= c + 8, or a witness at every c <= 10) agrees with rad(U) | rad(b) at every cell, and so does the alignment condition read directly (some K <= 8 at the first 400 multiples of h b^K; no K where the slope fails). The count of cells where the reduced numerator is smooth and U is not is at least 1 at bases 2 and 10. floor((u/v) n), gcd(u, v) = 1, u, v <= 12, at bases 2, 6, 10: read iff rad(u) | rad(b). floor((n + s)/v), v = 3, 5, 7, and n + omega, |omega| <= 3, at bases 2 and 10: read iff s = 0 and iff omega = 0. For g at base 10 the brute reader at t = 1..3 finds exceptions at c = 0, 1 and none at c = 2, and v_10(n*(10^J)) = J - 1 at J = 1..14. At base 2, where U = 10 is rough, v_2(n*(2^J)) does not climb: kill if it is at least J - 10 at some J in 20..40. Kill: one cell off. PK The least lookahead, at every read cell of PA, scanning t = 1.. max(3, t_ov) and J = 0..r + K + 6, t_ov the first t whose overflow interval holds a unit: c_scan >= c_deep, with a deep misaligned crossing exhibited at c_deep - 1 where c_deep >= 1; c_scan = digits_b(h) at every cell with K = 0, b not dividing h, h >= 2 and Delta <= (b - 1) b^delta; c_scan <= max(c_deep, delta + K) wherever Delta <= (b - 1) b^(delta + K). The counts of cells under each clause, and of cells at max(c_deep, delta + K - 1), are printed, not predicted. floor(n/3) + floor(n/9) at base 2 reads c_scan = 4 with its deep witness at t = 4, not below. Kill: one cell off a proved clause. PS The structural split: x, pi and P read at c = 0 by the brute tile reader at depths 1..4; x and pi each have a printed descent n < n' with f(n) > f(n'); P(n)/n takes a value within 0.01 of 1/b and the value 1. Kill: an exception at c = 0. PR THE REDUNDANT READER at (b, a) = (2, 1), (3, 2), (4, 2), (10, 6), (10, 9). R0, read first, the positive control: at balanced ternary (3, 1), where 2 rho - 1 = 0, the reader of y -> y/2 at the stream 1 0 0 ... is stuck at every depth to 12, and at (2, 1) it is not. R1: the j-digit values fill [-a R_j, a R_j] for j <= 5, and the children overlap by exactly (2 rho - 1) b^-(t+1). R2: the reader at lookahead max(0, ceil(log_b L + log_b(2a/(2a - b + 1)))) never sticks and nests, over 200 random streams to depth 30 (exact rationals), for y -> y/3, y -> 2y/5 and y -> -y/7, the mean (x + y)/2 and the product xy/rho. Kill: a stick at the formula, or R0 not sticking at (3, 1). PE THE HEDGE at (2, 1), (3, 1), (10, 6), (10, 9): every prefix to depth 5 (depth 3 at base 10) maps its tile onto its copy's tile, negated at a negative first nonzero digit; the all-zero tile holds both signs at every depth. At (2, 2) a prefix with first digit 1 holds a negative value. Kill: one prefix off. PP THE PURCHASE. (a) Over all prefix pairs at depth t <= 3, both orders are realized exactly when V' - V < 2 rho b^-t, and each tile's open-order set has 2K + 1 members away from the ends, three at (2, 1) and (10, 6), one at a non-redundant end (standard digits 0..b - 1); (b) the tile of 1 0 ... 0 holds values on both sides of 1/b at depth 1..10; (c) at every b = 2..10 and a with 2a + 1 > b and a <= b - 1, p | b, j = 1..4: counting uniform iff string uniform iff p | 2a + 1, and the counting bias at most 1/(2a R_j + 1); (d) the quotient's image over the all-zero y-tile is unbounded (it holds +-b^t at depth t), and D x/y with D = 1/2 is read at (2, 1) by R2's reader at its formula. Kill: one case off. PM THE PERIOD LAW over bases 2, 6, 10, multipliers 2..12 and 25, l = 1, 2 (3 at base 2), j = 1, 2, 4 (j = 1, 2 at base 10), both classes, three phases each: the exception count over b^Lam consecutive class members equals d floor(a (b^j - 1)/(b^j d)) exactly, and it is 0 iff a | b^Lam. The counting density at (b, a, l, j) = (10, 3, 1, 2), (6, 5, 1, 2), (2, 3, 1, 2), (10, 7, 2, 1) is within (2a + 2)/N of (1 - 1/a)/b^l over all N t'-digit P at the largest t' run; the log-weighted density comes within 2% of (1 - 1/a) H(xi)/b^l there. H > 1 at 99 interior grid points at b = 2, 3, 10. The Haar positive control: leading-digit 1 carries log_b 2; the counting mass of that tile moves under x -> 3x. Kill: one count off the formula, a zero off a | b^Lam, a density outside its band. FINDINGS (entered after the run; prints copied from it). - C0 holds, read first: floor(2n) at c = 0 and floor(n/3) at c = 1 by both readers, floor(3n) and floor((n + 1)/3) at no c <= 3. The two readers agree at 1368 of 1368 (sum cell, t, c). - PT holds: every tile at bases 2, 3, 10 is [P b^j, (P + 1) b^j), and the depth-2 tile of 4 at base 2 is [4, 5]. - PH holds at all 1595 (b, m, j). The trailing half ran on the pairs n, n + k b^j with n < min(b^j, 60) and k <= 3, not on every n < b^(j + 3): at b = 12, j = 4 that range is 3.6 * 10^7. - PZ holds: e(xy) - e(x) - e(y) takes [0, 1] at all three bases; the tiles [64, 128) and [1000, 2000) give difference exponents [0..5] and [0, 1, 2], signs -1, 0, 1; the prediction's "depth" of these tiles is their span, 6 and 3. - PC holds at all five systems. "Nothing off the coset" is the extension's form, V + b^t z, and was not enumerated; the per-prefix check is the reach check restated, since (x - V)/b^t runs over the same z. - PA holds: 42 of 171 cells read, the reader and the alignment condition each agreeing with rad(U) | rad(b) at 171 of 171. The crossing reader scans J over 0..25, 0..15 and 0..14 at bases 2, 6 and 10, not J <= c + 8; three of the six base-10 sums are weighted. The converse failures are floor(n/3) + floor(n/6) and floor(n/6) + floor(n/12) at bases 2 and 10, 3 floor(n/3) + floor(n/7) at base 10, and none at base 6. 273 maps floor((u/v) n) read iff rad(u) | rad(b); the phases and shifts read only at s = 0 and omega = 0. g at base 10, n < 10^6: 1552, 1103 and 0 exceptions at c = 0, 1, 2. v_10(n*(10^J)) = J - 1 at J = 1..14; v_2(n*(2^J)) is 1 at J = 1 mod 4 and 0 otherwise over J = 1..40. g(20) - 200/21 = -32/21. - PK holds: c_scan >= c_deep at all 42 read cells with a deep crossing needing exactly c_deep wherever c_deep >= 1; c_scan = digits_b(h) at all 30 law cells, the law's c_min bounding it from above; all 42 cells meet the shallow condition and sit at or under max(c_deep, delta + K). The sharper max(c_deep, delta + K - 1) holds at 42, with equality at 41. floor(n/3) + floor(n/9) at base 2: h = 9, c_deep = 4, t_ov = 4, c_scan = 4, decided by the crossing 135 of 15 * 2^2 at t = 4; to depth 3 the scan reads 3. Printed since a later reading: all 42 read cells have c_deep >= 1, so a deep crossing is sought at each; of C0's 1368 agreeing cells, 1130 have t + c below E, the rest agreeing because every input tile there is one number. - PS holds: x, pi and P have 0 exceptions at c = 0 over depths 1..4; x descends at (2, 3), pi at (10, 11); P(n)/n is 0.1010 at 99 and 1 at 100. Added at a later reading, the doc's counts on Z/2^t: 64 polynomial functions and 64 maps read at lookahead 0 at Z/4, 1024 against 16384 at Z/8, every polynomial function among them. - PP (a)'s open-order sizes are pooled over the depths, since at depth 1 no tile lies clear of the ends. - PR holds. R0, read first: balanced ternary commits 0 digits of y/2 at the stream 1 0 0 ... at lookahead 3; signed binary commits 12 of 12 at lookahead 0. R1 holds at all five systems; its cover and overlap half is rho = a/(b - 1)'s fixed-point algebra at t = 0, restated rather than built from tile_of. R2: no stick at the formula's lookahead, which is 0 for y/3 at (2, 1), 1 for y/3 at (10, 6), 1 for the mean everywhere and 2 for xy/rho at (2, 1), (3, 2), (4, 2). Base 10 ran 40 random streams per map, not 200. - PE holds at all four systems; at (2, 2) the tile of the prefix 1 is [-1/2, 3/2]. Its copy test is an identity at a positive first digit and tile_of's symmetry under negation at a negative one; the sign tests carry it. - PP holds. (a) Every tile clear of the ends has an open-order set of 3 at (2, 1), (10, 6) and (3, 2) (the standard end's tiles meet only at endpoints by definition, untested); the pairs read are those within 3K + 3 tiles of each other, at depths up to 3, and up to 2 at (10, 6). The iff itself is the interval algebra of (8)(i), which the check restates rather than tests. (b) holds at depths 1..10. (c) holds at all 132 (b, a, p, j). (d) the quotient reaches +-2^t on the all-zero tile, and D x/y at D = 1/2 is read at lookahead 3 on 100 streams with y >= 1/2. - PM holds: 1257 cases, every count on the formula and every zero exactly where a | b^Lam. The densities: counting 0.066667, 0.133333, 0.333336 and 0.008571 against 0.066667, 0.133333, 0.333333 and 0.008571 (off by at most 0.3 exceptions); log-weighted 0.114118, 0.167642, 0.353762 and 0.014364 against 0.114118, 0.167642, 0.353759 and 0.014365. The Haar control, run at bases 7 and 10 since at bases 2 and 3 tripling moves no leading digit: digit 1 carries 0.356207 and 0.301030, the same to 1e-5 after x -> 3x (asserted), while counting moves 0.1667 to 0.3889 and 0.1111 to 0.3704. SETTLED ON AUDIT (the argument above stays as frozen; these replace it). - (3) holds on a deep tile paired with itself, not on every pair of tiles: two far tiles fix the sign of x - y. [x = y], sign(x - y) and e(|x - y|) take every value on (T, T), T deep, at every depth. - (10)(d) D x/y is (1 + rho/D)-Lipschitz for general rho; 1 + 1/D is the rho = 1 case the script runs. - (11) needs l >= 1 and j >= 1. At l = 0 (theta = 0) b^Lam = 1 is not above a and s = 0 can be an exception (b = 10, a = 3, j = 1: all three m = 1, 2, 3); at j = 0 no tile is an exception while a need not divide b^Lam. The script runs only l >= 1, j >= 1. - (6)'s sharper max(c_deep, delta + K - 1) is read at t <= max(3, t_ov) and J <= r + K + 6 only. RUN RECORD: 37/37 checks, 20.5 s, peak commit 132 MB under a memory guard. """ import bisect import math import time from itertools import product CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) tail = f" ({detail})" if detail else "" print(f" {'PASS' if ok else 'FAIL'} {name}{tail}") # ---- digits ---- def ndig(n, b): if b == 2: return n.bit_length() if b == 10: return len(str(n)) if n else 0 d = 0 while n: n //= b d += 1 return d def vb(n, b): k = 0 while n % b == 0: n //= b k += 1 return k def primes_of(n): ps, p = set(), 2 while p * p <= n: while n % p == 0: ps.add(p) n //= p p += 1 if n > 1: ps.add(n) return ps def smooth(u, b): return primes_of(u) <= primes_of(b) def tile_key(n, b, t): d = ndig(n, b) return d, n // b ** max(0, d - t) # ---- maps: (f, p, q, C) with lambda = p/q and |f(n) - lambda n| <= C ---- def sum_map(terms): l = math.lcm(*[v for _, v in terms]) U = sum(w * l // v for w, v in terms) g = math.gcd(U, l) C = (sum(w * (v - 1) * (l // v) for w, v in terms), l) return Map(lambda n: sum(w * (n // v) for w, v in terms), U // g, l // g, C), U def frac_map(u, v): return Map(lambda n: u * n // v, u, v, (v - 1, v)) def phase_map(s, v): return Map(lambda n: (n + s) // v, 1, v, (max(s, v - s), v)) def shift_map(w): return Map(lambda n: n + w, 1, 1, (abs(w), 1)) class Map: """f nondecreasing, lambda = p/q, |f(n) - lambda n| <= C = Cn/Cd.""" def __init__(self, f, p, q, C): self.f, self.p, self.q = f, p, q Cn, Cd = C # Delta = ceil(C/lambda) + 1 self.D = -(-(Cn * q) // (Cd * p)) + 1 def crossing(self, B): f = self.f n = max(1, B * self.q // self.p - self.D - 1) while n > 1 and f(n - 1) >= B: n -= 1 while f(n) < B: n += 1 return n def c_need(self, b, t, M, J): """Least c at which the crossing of M b^J is no depth-t witness.""" n = self.crossing(M * b ** J) if n <= 1 or self.f(n - 1) < 1: return 0, n return max(0, ndig(n, b) - t - vb(n, b)), n def scan(self, b, ts, Js): best, wit = 0, None for t in ts: for M in range(1, b ** t): if M % b == 0: continue for J in Js: c, n = self.c_need(b, t, M, J) if c > best: best, wit = c, (t, M, J, n) return best, wit def slope(self, b): """(r, h) with lambda = b^r / h, r least, or None.""" r = 0 while b ** r % self.p: r += 1 if r > 64: return None return r, self.q * b ** r // self.p def alignment_K(self, b, Kmax=8, count=400): sp = self.slope(b) if sp is None: return None r, h = sp f, p, q = self.f, self.p, self.q for K in range(Kmax + 1): step = h * b ** K if all(f(N) * q >= p * N > f(N - 1) * q for N in range(step, step * (count + 1), step)): return K return None def J_range(b): return range(0, {2: 26, 6: 16, 10: 15}[b]) # ---- the brute tile reader ---- def brute_exceptions(vals, b, t, c): img = {} for n in range(1, len(vals)): y = vals[n] if y >= 1: img.setdefault(tile_key(n, b, t + c), set()).add( tile_key(y, b, t)) return sum(1 for s in img.values() if len(s) > 1) def values(f, b, E): return [0] + [f(n) for n in range(1, b ** E)] def cells(): out = [] for b in (2, 6, 10): for v1 in range(2, 13): for v2 in range(v1 + 1, 13): out.append((b, [(1, v1), (1, v2)])) for terms in ([(2, 3), (1, 7)], [(3, 3), (1, 7)], [(2, 3), (2, 7)], [(1, 2), (1, 5), (1, 10)], [(1, 2), (1, 3), (1, 7)], [(1, 3), (1, 7), (1, 21)]): out.append((10, terms)) return out def name_of(terms): return " + ".join((f"{w} " if w > 1 else "") + f"floor(n/{v})" for w, v in terms) # ---- C0 ---- def section_0(): print("C0 controls: the brute reader and the crossing reader") ok = True rows = [("floor(2n)", 2, frac_map(2, 1), 0, 12), ("floor(3n)", 2, frac_map(3, 1), None, 12), ("floor(n/3)", 10, frac_map(1, 3), 1, 5), ("floor((n+1)/3)", 10, phase_map(1, 3), None, 5)] for name, b, m, want, E in rows: vals = values(m.f, b, E) got = next((c for c in range(4) if all(brute_exceptions(vals, b, t, c) == 0 for t in (1, 2, 3))), None) best, _ = m.scan(b, (1, 2, 3), J_range(b)) cr = best if best <= 10 else None print(f" {name:15s} base {b:2d}: brute least c = {got}, " f"crossing reader {cr} (want {want})") ok &= got == want and cr == want check("the four controls read as predicted by both readers", ok) agree = total = live = 0 for b, terms in cells(): m, U = sum_map(terms) E = {2: 13, 6: 5, 10: 4}[b] vals = values(m.f, b, E) top = b ** E for t in (1, 2): needs = [] for M in range(1, b ** t): if M % b == 0: continue J = 0 while M * b ** J <= vals[-1]: cn, n = m.c_need(b, t, M, J) if n < top: needs.append(cn) J += 1 for c in range(4): brute_ok = brute_exceptions(vals, b, t, c) == 0 total += 1 agree += brute_ok == all(x <= c for x in needs) # at t + c >= E every input tile below b^E is one number, # so the brute reader finds no exception there live += t + c < E check("brute and crossing readers agree at every sum cell, t = 1, 2, " "c <= 3", agree == total, f"{agree} of {total}, {live} with " f"input depth t + c below E") # ---- PT ---- def section_t(): print("PT the leading-tile lemma") ok = True for b, E in ((2, 12), (3, 7), (10, 4)): for t in range(1, 5): tiles = {} for n in range(1, b ** E): tiles.setdefault(tile_key(n, b, t), []).append(n) for (d, P), ns in tiles.items(): j = max(0, d - t) ok &= ns == list(range(P * b ** j, (P + 1) * b ** j)) if len(ns) >= 2: ok &= all(len({n % m for n in ns}) > 1 for m in range(2, 13)) check("every tile is [P b^j, (P + 1) b^j), j = max(0, e + 1 - t), " "and no tile of length >= 2 decides n mod m, m = 2..12", ok) t4 = [n for n in range(1, 64) if tile_key(n, 2, 2) == tile_key(4, 2, 2)] print(f" base 2, the depth-2 tile of 4: {t4}") check("[4, 6) is a depth-2 tile holding no multiple of 7", t4 == [4, 5] and all(n % 7 for n in t4)) # ---- PH ---- def section_h(): print("PH the two-ends law") bad = [] n_cases = 0 for b in range(2, 13): for m in range(2, 31): for j in range(5): L = b ** j pred = L % m == 0 lead = True for P in range(1, b * b): A = P * L cnt = {(A + L - 1 - r) // m - (A - 1 - r) // m for r in range(m)} lead &= len(cnt) == 1 trail = all((n + k * L) % m == n % m for n in range(min(L, 60)) for k in (1, 2, 3)) n_cases += 1 if not pred == lead == trail: bad.append((b, m, j)) print(f" {n_cases} (b, m, j) read; disagreements: {bad[:5]}") check("uniform on every span-j leading tile with a one- or two-digit " "prefix iff m | b^j iff the last j digits read n mod m", not bad) # ---- PZ ---- def section_z(): print("PZ the crown exchange") ok = True for b, X in ((2, 2 ** 10), (3, 3 ** 7), (10, 500)): pw = [1] while pw[-1] <= X * X: pw.append(pw[-1] * b) ex = [0] + [ndig(n, b) - 1 for n in range(1, X)] seen = set() for x in range(1, X): for y in range(1, X): seen.add(bisect.bisect_right(pw, x * y) - 1 - ex[x] - ex[y]) print(f" base {b:2d}, x, y < {X}: e(xy) - e(x) - e(y) takes " f"{sorted(seen)}") ok &= seen == {0, 1} check("a product's exponent is the factors' to one bit", ok) ok = True for b, lo, j in ((2, 64, 6), (10, 1000, 3)): diffs = {x - y for x in range(lo, lo + b ** j) for y in range(lo, lo + b ** j)} exps = {ndig(abs(d), b) - 1 for d in diffs if d} signs = {(d > 0) - (d < 0) for d in diffs} print(f" base {b:2d}, tile [{lo}, {lo + b ** j}): difference " f"exponents {sorted(exps)}, signs {sorted(signs)}") ok &= exps == set(range(j)) and signs == {-1, 0, 1} check("one deep tile holds every difference exponent below its span, " "both signs and 0", ok) # ---- PC ---- def write_digits(n, b, a): ds = [] while not -a <= n <= a: d = n % b if d > a: d -= b ds.append(d) n = (n - d) // b if n: ds.append(n) return ds def section_c(): print("PC the coset rigidity") ok = True for b, a in ((2, 1), (3, 1), (4, 2), (10, 5), (10, 6)): rt = True for n in range(-10 ** 4, 10 ** 4 + 1): ds = write_digits(n, b, a) rt &= (sum(d * b ** k for k, d in enumerate(ds)) == n and all(-a <= d <= a for d in ds)) Z = {0} for k in range(5): Z = {z + d * b ** k for z in Z for d in range(-a, a + 1)} full = all(z in Z for z in range(-b ** 3, b ** 3 + 1)) eq = True for t in (1, 2, 3): pref = {0} for k in range(t): pref = {v + d * b ** k for v in pref for d in range(-a, a + 1)} X = b ** (t + 3) for V in pref: for x in range(V - X, V + X + 1, b ** t): eq &= (x - V) // b ** t in Z # nothing off the coset: the extension adds b^t z print(f" (b, a) = ({b:2d}, {a}): round trip {rt}; five-digit " f"extensions hold [-b^3, b^3]: {full}; every prefix's " f"completions reach its coset within b^(t+3): {eq}") ok &= rt and full and eq check("the completions of every trailing prefix of length <= 3 " "reach its coset within b^(t+3)", ok) # ---- PA ---- READ = [] def section_a(): print("PA the affine class") t0 = time.time() agree = agree_K = 0 conv = {2: [], 6: [], 10: []} for b, terms in cells(): m, U = sum_map(terms) best, _ = m.scan(b, (1, 2, 3), J_range(b)) reader = best <= 10 crit = smooth(U, b) K = m.alignment_K(b) agree += reader == crit agree_K += (K is not None) == crit if m.slope(b) is not None and not crit: conv[b].append(name_of(terms)) if crit: READ.append((b, terms, best)) n = len(cells()) print(f" {n} cells, {len(READ)} read; converse failures (slope " f"holds, U rough): " + "; ".join(f"base {b}: {len(v)} {v}" for b, v in conv.items())) check("the crossing reader agrees with rad(U) | rad(b) at every cell", agree == n, f"{agree} of {n}") check("the alignment condition read directly agrees at every cell", agree_K == n, f"{agree_K} of {n}") check("converse failures exist at bases 2 and 10", conv[2] and conv[10]) ok = True cnt = 0 for b in (2, 6, 10): for u in range(1, 13): for v in range(1, 13): if math.gcd(u, v) != 1: continue m = frac_map(u, v) best, _ = m.scan(b, (1, 2), J_range(b)) ok &= (best <= 10) == smooth(u, b) cnt += 1 check("floor((u/v) n) is read iff rad(u) | rad(b)", ok, f"{cnt} maps at bases 2, 6, 10") ok = True for b in (2, 10): for v in (3, 5, 7): for s in range(v): best, _ = phase_map(s, v).scan(b, (1, 2), J_range(b)) ok &= (best <= 10) == (s == 0) for w in range(-3, 4): best, _ = shift_map(w).scan(b, (1, 2), J_range(b)) ok &= (best <= 10) == (w == 0) check("floor((n + s)/v) is read iff s = 0 and n + omega iff omega = 0", ok) g, U = sum_map([(1, 3), (1, 7)]) vals = values(g.f, 10, 6) exc = [sum(brute_exceptions(vals, 10, t, c) for t in (1, 2, 3)) for c in range(3)] print(f" g = floor(n/3) + floor(n/7), base 10, n < 10^6: brute " f"exceptions at c = 0, 1, 2: {exc}") check("g is read at c = 2 and not at c = 0 or 1 (n < 10^6, t <= 3)", exc[0] > 0 and exc[1] > 0 and exc[2] == 0) v10 = [vb(g.crossing(10 ** J), 10) for J in range(1, 15)] print(f" v_10(n*(10^J)), J = 1..14: {v10}") check("v_10(n*(10^J)) = J - 1", v10 == list(range(14))) v2 = [vb(g.crossing(2 ** J), 2) for J in range(1, 41)] print(f" v_2(n*(2^J)), J = 1..40: {v2}") check("at base 2 the crossing's depth does not climb with J", all(v2[J - 1] < J - 10 for J in range(20, 41))) print(f" g(20) - 200/21 = {vals[20] * 21 - 200}/21") print(f" [{time.time() - t0:.1f} s]") # ---- PK ---- def section_k(): print("PK the least lookahead") t0 = time.time() ok_floor = ok_wit = ok_law = ok_up = True n_law = n_up = n_sharp = n_meet = n_deep = 0 for b, terms, _ in READ: m, _ = sum_map(terms) r, h = m.slope(b) K = m.alignment_K(b) dl, mu = ndig(h, b), vb(h, b) hp = h // b ** mu c_deep = ndig(hp, b) - (hp == 1) t_ov = 1 if hp >= 2: while not any(math.gcd(M, b) == 1 for M in range(-(-b ** (dl + t_ov - 1) // h), b ** t_ov)): t_ov += 1 ts = range(1, max(3, t_ov) + 1) c_scan, wit = m.scan(b, ts, range(0, r + K + 7)) ok_floor &= c_scan >= c_deep if c_deep >= 1: n_deep += 1 found = False for t in ts: for M in range(1, b ** t): if math.gcd(M, b) != 1: continue c, _ = m.c_need(b, t, M, r + K + 2) found |= c == c_deep ok_wit &= found D = m.D if K == 0 and h % b and h >= 2 and D <= (b - 1) * b ** dl: n_law += 1 ok_law &= c_scan == dl if D <= (b - 1) * b ** (dl + K): n_up += 1 ok_up &= c_scan <= max(c_deep, dl + K) n_sharp += c_scan <= max(c_deep, dl + K - 1) n_meet += c_scan == max(c_deep, dl + K - 1) if (b, terms) == (2, [(1, 3), (1, 9)]): c3, _ = m.scan(b, range(1, 4), range(0, r + K + 7)) print(f" floor(n/3) + floor(n/9), base 2: h = {h}, " f"c_deep = {c_deep}, t_ov = {t_ov}, c_scan = {c_scan}, " f"deciding crossing (t, M, J, n*) = {wit}; to depth 3 " f"c_scan = {c3}") print(f" {len(READ)} read cells, {n_deep} with c_deep >= 1 and a " f"deep crossing sought; law cells {n_law}; cells under the " f"shallow condition {n_up}; c_scan <= max(c_deep, delta + K - 1) " f"at {n_sharp}, equal at {n_meet}") check("c_scan >= c_deep at every read cell", ok_floor) check("a deep crossing needs exactly c_deep at every cell with " "c_deep >= 1", ok_wit) check("c_scan = digits_b(h), the law's c_min, at every law cell", ok_law) check("c_scan <= max(c_deep, delta + K) under the shallow condition", ok_up) print(f" [{time.time() - t0:.1f} s]") # ---- PS ---- def section_s(): print("PS the structural split") def x2(n): e = n.bit_length() - 1 return n ^ (1 << (e - 1)) if e >= 1 else n def pi10(n): s = str(n) if len(s) < 2: return n return int(s[0] + str(9 - int(s[1])) + s[2:]) def pow10(n): return 10 ** (len(str(n)) - 1) ok = True for name, f, b, E in (("x", x2, 2, 12), ("pi", pi10, 10, 5), ("P", pow10, 10, 5)): vals = values(f, b, E) exc = sum(brute_exceptions(vals, b, t, 0) for t in range(1, 5)) desc = next(((n, n + 1) for n in range(1, b ** E - 1) if vals[n] > vals[n + 1]), None) dv = desc and (vals[desc[0]], vals[desc[1]]) print(f" {name:2s} base {b:2d}: exceptions at c = 0 over depths " f"1..4: {exc}; first descent {desc} -> {dv}") ok &= exc == 0 if name != "P": ok &= desc is not None else: ok &= desc is None ratios = [pow10(n) / n for n in (99, 999, 100)] print(f" P(n)/n at 99, 999, 100: " f"{', '.join(f'{x:.4f}' for x in ratios)}") ok &= abs(ratios[0] - 0.1) < 0.01 and ratios[2] == 1 check("x, pi and P are read at c = 0; x and pi are not monotone; " "P(n)/n is near 1/b at 99 and 1 at 100", ok) # Z/2^t: the polynomial functions (every polynomial with five # coefficients evaluated) against the maps read at lookahead 0, whose # value mod 2^i reads only x mod 2^i, counted digit by digit counts = {} for t in (2, 3): n = 2 ** t polys = {tuple(sum(c * x ** i for i, c in enumerate(cs)) % n for x in range(n)) for cs in product(range(n), repeat=5)} def causal(f): return all(f[x] % 2 ** i == f[x % 2 ** i] % 2 ** i for i in range(1, t + 1) for x in range(n)) brute = (sum(map(causal, product(range(n), repeat=n))) if t == 2 else None) counts[t] = (len(polys), math.prod(2 ** (2 ** i) for i in range(1, t + 1)), brute, all(map(causal, polys))) print(f" Z/{n}: {counts[t][0]} polynomial functions, " f"{counts[t][1]} maps read at lookahead 0 (brute: " f"{brute}), every polynomial one of them: {counts[t][3]}") check("Z/4: 64 polynomial functions, all 64 maps read at lookahead 0; " "Z/8: 2^10 against 2^14", counts[2] == (64, 64, 64, True) and counts[3] == (2 ** 10, 2 ** 14, None, True)) # ---- the redundant leading end: digits -a..a, 2a + 1 > b, y in [-rho, rho] import random from fractions import Fraction as Fr def rho_of(b, a): return Fr(a, b - 1) def stream_value(ds, b): return sum(Fr(d, b ** (k + 1)) for k, d in enumerate(ds)) def tile_of(ds, b, a): V, r = stream_value(ds, b), rho_of(b, a) / b ** len(ds) return V - r, V + r def lookahead_for(L, b, a): c, need = 0, L * Fr(2 * a, 2 * a - b + 1) while b ** c < need: c += 1 return c def run_reader(F, streams, b, a, c, depth, dom=None): """Commit output digits of F at lookahead c; return the depth reached (depth when never stuck). F maps a list of input intervals to the image interval; dom clips each input interval to the map's domain.""" rho = rho_of(b, a) W = Fr(0) for t in range(depth): boxes = [] for i, s in enumerate(streams): lo, hi = tile_of(s[:t + 1 + c], b, a) if dom: lo, hi = max(lo, dom[i][0]), min(hi, dom[i][1]) boxes.append((lo, hi)) ilo, ihi = F(boxes) step = Fr(1, b ** (t + 1)) r = rho * step d_lo = math.ceil((ihi - W - r) / step) d_hi = math.floor((ilo - W + r) / step) d_lo, d_hi = max(d_lo, -a), min(d_hi, a) if d_lo > d_hi: return t W += d_lo * step return depth def scale(q): def F(boxes): lo, hi = boxes[0] return min(q * lo, q * hi), max(q * lo, q * hi) return F def mean(boxes): (a0, a1), (b0, b1) = boxes return (a0 + b0) / 2, (a1 + b1) / 2 def corners(g): def F(boxes): (a0, a1), (b0, b1) = boxes vals = [g(x, y) for x in (a0, a1) for y in (b0, b1)] return min(vals), max(vals) return F def section_r(): print("PR the redundant reader") s3 = [1] + [0] * 40 stuck3 = run_reader(scale(Fr(1, 2)), [s3], 3, 1, 3, 12) stuck2 = run_reader(scale(Fr(1, 2)), [s3], 2, 1, 0, 12) print(f" R0 y -> y/2 at the stream 1 0 0 ...: balanced ternary " f"(3, 1) at lookahead 3 commits {stuck3} digits; (2, 1) at " f"lookahead 0 commits {stuck2} of 12") check("R0: balanced ternary sticks, signed binary does not", stuck3 == 0 and stuck2 == 12) systems = ((2, 1), (3, 2), (4, 2), (10, 6), (10, 9)) ok = True for b, a in systems: vals = {0} for j in range(1, 6): vals = {b * v + d for v in vals for d in range(-a, a + 1)} R = (b ** j - 1) // (b - 1) ok &= vals == set(range(-a * R, a * R + 1)) rho = rho_of(b, a) ends = (-a * Fr(1, b) - rho / b, a * Fr(1, b) + rho / b) overlap = (Fr(0, 1) + rho / b) - (Fr(1, b) - rho / b) ok &= ends == (-rho, rho) and overlap == (2 * rho - 1) / b check("R1: j-digit values fill [-a R_j, a R_j]; the children cover " "the tile and overlap by (2 rho - 1) b^-(t+1)", ok) rng = random.Random(20260924) ok = True rows = [] for b, a in systems: rho = rho_of(b, a) maps = [("y/3", scale(Fr(1, 3)), Fr(1, 3), 1), ("2y/5", scale(Fr(2, 5)), Fr(2, 5), 1), ("-y/7", scale(Fr(-1, 7)), Fr(1, 7), 1), ("(x+y)/2", mean, Fr(1), 2), ("xy/rho", corners(lambda x, y, r=rho: x * y / r), Fr(2), 2)] for name, F, L, k in maps: c = lookahead_for(L, b, a) worst = 30 for _ in range(200 if b < 10 else 40): ss = [[rng.randint(-a, a) for _ in range(30 + c + 1)] for _ in range(k)] worst = min(worst, run_reader(F, ss, b, a, c, 30)) rows.append((b, a, name, c, worst)) ok &= worst == 30 for b, a in systems: print(f" ({b:2d}, {a}): " + ", ".join( f"{n} c={c}" for bb, aa, n, c, w in rows if (bb, aa) == (b, a))) check("R2: the reader at the formula's lookahead never sticks", ok) return rng def section_e(): print("PE the hedge") ok = True for b, a, depth in ((2, 1, 5), (3, 1, 5), (10, 6, 3), (10, 9, 3)): prefixes = [[]] for t in range(1, depth + 1): prefixes = [p + [d] for p in prefixes for d in range(-a, a + 1)] for p in prefixes: lo, hi = tile_of(p, b, a) first = next((d for d in p if d), 0) if first == 0: ok &= lo < 0 < hi continue ok &= lo >= 0 if first > 0 else hi <= 0 q = [-d for d in p] if first < 0 else p alo, ahi = (lo, hi) if first > 0 else (-hi, -lo) ok &= tile_of(q, b, a) == (alo, ahi) check("|y| is read at lookahead 0 and the all-zero tile holds both " "signs, at (2, 1), (3, 1), (10, 6), (10, 9)", ok) lo, hi = tile_of([1], 2, 2) print(f" (2, 2): the tile of the prefix 1 is [{lo}, {hi}]") check("at a > b - 1 a positive first digit holds negative values", lo < 0) def section_p(rng): print("PP what the purchase spends") ok = True for b, a, tmax in ((2, 1, 3), (10, 6, 2), (3, 2, 3)): rho = rho_of(b, a) K = math.ceil(Fr(2 * a, b - 1)) - 1 seen = set() for t in range(1, tmax + 1): R = (b ** t - 1) // (b - 1) ks = range(-a * R, a * R + 1) r = rho / b ** t sizes = set() for k in ks: if abs(k) > a * R - 2 * K - 1: continue V = Fr(k, b ** t) opn = 0 for k2 in range(k - 3 * K - 3, k + 3 * K + 4): V2 = Fr(k2, b ** t) both = V2 - r < V + r and V - r < V2 + r ok &= both == (abs(V2 - V) < 2 * r) opn += both sizes.add(opn) seen |= sizes ok &= seen == {2 * K + 1} print(f" ({b:2d}, {a}): open-order sets of sizes {sorted(seen)}, " f"2K + 1 = {2 * K + 1}") check("(a) both orders iff |V' - V| < 2 rho b^-t; 2K + 1 tiles open", ok) ok = True for b, a in ((2, 1), (10, 6), (10, 9)): for t in range(1, 11): lo, hi = tile_of([1] + [0] * (t - 1), b, a) ok &= lo < Fr(1, b) < hi check("(b) the tile of 1 0 ... 0 holds 1/b in its interior at depths 1..10", ok) bad, cases = [], 0 for b in range(2, 11): for a in range(1, b): if 2 * a + 1 <= b: continue for p in sorted(primes_of(b)): for j in range(1, 5): R = (b ** j - 1) // (b - 1) cnt = [0] * p for z in range(-a * R, a * R + 1): cnt[z % p] += 1 N = 2 * a * R + 1 dist = [1] + [0] * (p - 1) for k in range(j): new = [0] * p for rr in range(p): for d in range(-a, a + 1): new[(rr + d * b ** k) % p] += dist[rr] dist = new cu, su = len(set(cnt)) == 1, len(set(dist)) == 1 bias = max(abs(Fr(x, N) - Fr(1, p)) for x in cnt) cases += 1 if not (cu == su == ((2 * a + 1) % p == 0) and bias < Fr(1, N)): bad.append((b, a, p, j)) print(f" {cases} (b, a, p, j) read; off: {bad[:5]}") check("(c) the leak: counting and string uniform iff p | 2a + 1", not bad) ok = True for t in range(1, 8): xlo, xhi = tile_of([1], 2, 1) ylo, yhi = tile_of([0] * t, 2, 1) ok &= xhi / yhi == 2 ** t and xhi / ylo == -(2 ** t) D = Fr(1, 2) c = lookahead_for(1 + 1 / D, 2, 1) worst = 30 for _ in range(100): xs = [rng.randint(-1, 1) for _ in range(31 + c)] ys = [1] + [rng.randint(0, 1) for _ in range(30 + c)] worst = min(worst, run_reader( corners(lambda x, y: D * x / y), [xs, ys], 2, 1, c, 30, dom=[(Fr(-1), Fr(1)), (D, Fr(1))])) print(f" D x/y at D = 1/2, (2, 1): lookahead {c}, commits " f"{worst} of 30 on every stream") check("(d) the quotient is unbounded on the all-zero y-tile and read " "given y >= D", ok and worst == 30) # ---- the period law and the singularity's own measure ---- def exceptional(m, a, b, j, t): lo, hi = a * m * b ** j, a * ((m + 1) * b ** j - 1) return tile_key(lo, b, t) != tile_key(hi, b, t) def section_m(): print("PM the period law and the measure") t0 = time.time() bad, zero_bad, scopes = [], [], 0 plan = {2: ((1, 2, 3), (1, 2, 4)), 6: ((1, 2), (1, 2, 4)), 10: ((1, 2), (1, 2))} for b, (ls, js) in plan.items(): for a in list(range(2, 13)) + [25]: al = ndig(a, b) - 1 for l in ls: for j in js: for th in (0, 1): if th == 1 and b ** al == a: continue Lam = l + al + th P = b ** Lam tp = l + 1 while True: cut = -(-b ** (tp + al) // a) lo_c, hi_c = ((b ** (tp - 1), cut) if th == 0 else (cut, b ** tp)) if hi_c - lo_c >= P + P // 2 + 2: break tp += 1 t = tp - l d = math.gcd(a, P) want = d * ((a * (b ** j - 1)) // (b ** j * d)) for start in (lo_c, lo_c + 1, lo_c + P // 2): got = sum(exceptional(m, a, b, j, t) for m in range(start, start + P)) scopes += 1 if got != want: bad.append((b, a, l, j, th, start, got, want)) if (want == 0) != (P % a == 0): zero_bad.append((b, a, l, j, th)) print(f" {scopes} cases read; off the formula: {bad[:3]}; zero " f"locus off a | b^Lam: {zero_bad[:3]} [{time.time() - t0:.1f} s]") check("the exception count over every class is d floor(a (b^j " "- 1)/(b^j d))", not bad) check("the count is 0 iff a | b^Lam", not zero_bad) def H(x, b): return b ** (x - 1) * (1 + (b - 1) * (1 - x)) ok_c = ok_h = True for b, a, l, j, tp in ((10, 3, 1, 2, 6), (6, 5, 1, 2, 7), (2, 3, 1, 2, 18), (10, 7, 2, 1, 6)): t = tp - l ms = range(b ** (tp - 1), b ** tp) N = len(ms) exc = [m for m in ms if exceptional(m, a, b, j, t)] cnt = Fr(len(exc)) law = Fr(a - 1, a) / b ** l ben = sum(math.log((m + 1) / m, b) for m in exc) x = math.log(a, b) % 1 ben_law = (1 - 1 / a) * H(x, b) / b ** l print(f" (b, a, l, j) = ({b}, {a}, {l}, {j}), t' = {tp}: " f"counting {float(cnt / N):.6f} vs {float(law):.6f} " f"(off by {float(abs(cnt - law * N)):.1f} of {2 * a + 2} " f"allowed); log-weighted {ben:.6f} vs {ben_law:.6f}") ok_c &= abs(cnt - law * N) <= 2 * a + 2 ok_h &= abs(ben / ben_law - 1) < 0.02 check("the counting density is (1 - 1/a)/b^l within (2a + 2)/N", ok_c) check("the log-weighted density is (1 - 1/a) H(xi)/b^l within 2%", ok_h) hump = all(H(k / 100, b) > 1 for b in (2, 3, 10) for k in range(1, 100)) check("H > 1 at 99 interior points at bases 2, 3 and 10", hump) ok = True for b in (7, 10): tp = 5 if b == 10 else 6 ms = range(b ** (tp - 1), b ** tp) haar1 = sum(math.log((m + 1) / m, b) for m in ms if tile_key(m, b, 1)[1] == 1) haar3 = sum(math.log((m + 1) / m, b) for m in ms if tile_key(3 * m, b, 1)[1] == 1) cnt1 = sum(1 for m in ms if tile_key(m, b, 1)[1] == 1) / len(ms) cnt3 = sum(1 for m in ms if tile_key(3 * m, b, 1)[1] == 1) / len(ms) print(f" base {b:2d}: leading digit 1 carries Haar " f"{haar1:.6f} (log_b 2 = {math.log(2, b):.6f}), after x -> 3x " f"{haar3:.6f}; counting {cnt1:.4f}, after x -> 3x {cnt3:.4f}") ok &= (abs(haar1 - math.log(2, b)) < 1e-6 and abs(haar3 - math.log(2, b)) < 1e-5 and abs(cnt3 - cnt1) > 0.05) check("Haar keeps an arc's mass under x -> 3x; counting moves it", ok) def main(): t0 = time.time() section_0() section_t() section_h() section_z() section_c() section_a() section_k() section_s() rng = section_r() section_e() section_p(rng) section_m() print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, " f"{time.time() - t0:.1f} s") raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()