reading.py

"""
reading.py -- which maps a digit-by-digit reader computes at bounded
lookahead, what the numeration's tiles charge for it, and which place
pays for a wall.

QUESTION. A NUMERATION writes the points of a complete metric space X
as digit streams: its depth-t TILES C_t are the sets of points sharing
a t-digit prefix, nested, with mesh delta_t -> 0 and Lebesgue number
l_t (every set of diameter < l_t lies in one depth-t tile). A reader
of f at lookahead c sees an input tile at depth t + c and must commit
an output tile at depth t holding the image, the commitments nesting.
Which f can be read at bounded c, what does the tiles' shape charge,
and for the integer maps n -> mn and n -> floor(n/m), what decides?
The integer and polynomial numerations are the specimens: base b
(trailing digits of n, completing to the b-adic integers), the
primorial chain (n mod p_1 p_2 ... p_t, completing to the product of
the F_p), leading base b (the reals by their high digits), Zeckendorf
and the d-bonacci numerations (trailing, completing to an odometer or
a torus translation), and over F_q[x] both the trailing x-adic
numeration and the leading one at the place at infinity.

THE ARGUMENT (written before this script).
  (1) THE READING LEMMA. If f is L-Lipschitz, a depth-(t + c) tile
      has image of diameter <= L delta_{t+c}, which lies in one
      depth-t tile once L delta_{t+c} < l_t. Where tiles nest and the
      choice is made consistently, this per-level fit is a reader.
      Three tile shapes give three regimes: BALLS of an ultrametric
      (l_t = delta_t, the fit costs log_b L digits and nothing more);
      a PARTITION of a connected space (l_t = 0, the lemma is silent,
      readability is a per-map alignment question); an OVERLAPPING
      cover with l_t = rho delta_t (the fit costs a margin log_b(1/rho)
      on top).
  (2) THE BALL REGIME IS EVERY NON-ARCHIMEDEAN PLACE'S. In an
      ultrametric two points at distance < r lie in the same ball of
      radius r, so a numeration whose depth-t tiles are the balls of
      radius delta_t has l_t = delta_t. Every completion of Q or F_q(x)
      at a place other than the archimedean one is ultrametric, and its
      digit numeration's tiles are its balls. So a WALL -- an input
      point where a map Lipschitz in the place's own metric commits no
      output at any bounded lookahead -- needs a partition of a
      connected space, and among the completions of Q and F_q(x) only
      R is connected. The leading base-b numeration
      of R is the one numeration here with walls; the p-adic (char 0)
      and x-adic or 1/x-adic (char p) numerations have none. This is
      the question a clause priced at the archimedean place owes: at
      the carries and at a bundle's capacity the characteristic owned
      the price; here the PLACE does, since Q_p carries and still
      reads every scaling at bounded lookahead.
  (3) THE WALL CRITERION. At a partition cover of an interval with a
      rational vertex set B (the tile endpoints, which stay endpoints
      at every deeper level), take f continuous and strictly monotone
      and y irrational. If f(y) is not in B, f(y) lies interior to its
      tile at every depth and the image interval of a fine enough input
      tile fits: emission grows without bound. If f(y) is in B, every
      input tile around y has image straddling f(y), whose two sides
      agree only to the vertex's own depth: emission freezes at a
      constant. The permanent walls of f are f^-1(B) minus B.
  (4) THE LIPSCHITZ CRITERION. On a trailing numeration the agreement
      ultrametric is dist(y, z) = b^-(agreement depth), and "agreement
      to t + c forces image agreement to t" is dist(fy, fz) <= b^c
      dist(y, z).
      So f is readable at lookahead c iff it is b^c-Lipschitz, and a
      map on a dense subset extends to the completion with the same
      constant. Continuity is not enough: at a compact completion it
      buys a modulus s(t), and bounded lookahead needs s(t) <= t + c.
      Three classes: LIPSCHITZ, MIDDLE (continuous, lookahead growing
      with depth) and DISCONTINUOUS. The decimation D(n) = sum over
      j >= 0 of n_2j 2^j at base 2, n_j the digit of n at position j,
      needs input digits 0..2t - 2 for output digits 0..t - 1, so
      c_min(D, t) = t - 1: MIDDLE is inhabited.
  (5) THE DIVISION CRITERION ON A CHAIN. Let a trailing numeration's
      tiles be the classes n mod M_t for a divisor chain M_1 | M_2 |
      ... . Multiplication by m is 1-Lipschitz. floor(n/m) is readable
      at lookahead c at depth t iff m M_t divides M_{t+c}: if it does,
      n mod m is fixed by n mod M_{t+c}, and the quotients of inputs
      agreeing there differ by a multiple of M_{t+c}/m, which M_t
      divides; if not, some residue r < m has floor((r + M_{t+c})/m)
      - floor(r/m) not divisible by M_t, and the pair (r, r + M_{t+c})
      agrees at depth t + c and not after division. At base b this is
      m | b^c, bounded for every t iff rad(m) | rad(b). At the primorial
      chain m p_t# | p_{t+c}# holds iff m is squarefree with every prime
      in (p_t, p_{t+c}], so for each m >= 2 it fails at every depth from
      the index of m's least prime on: the primorial completion reads no floor
      division. Over F_q[x] the same algebra runs with polynomial
      division (the remainder has degree below deg m, so it is fixed
      by the residue mod m), and at base x the criterion is m = u x^j,
      u a nonzero constant.
  (6) NOT A TOPOLOGICAL RING (the comb). Take the d-bonacci numeration, q_k =
      q_(k-1) + ... + q_(k-d), q_j = 2^j for j < d, greedy digits.
      2 q_k = q_(k+1) + q_(k-d) walks a carry DOWN d places, so the
      step-(d + 1) comb T_K = q_d + q_(2d+1) + ... + q_K doubles to a
      step-d comb whose bottom cycles through d phases as K steps by
      d + 1. T_K and T_(K+d+1) agree to depth K + d + 1, and their
      doubles differ at a digit <= d - 2, at every K: x2 has no
      continuous extension, so the completion carries no continuous
      addition extending the integers'. d = 2 is Zeckendorf. The units
      read: n -> n + 1 at lookahead 1 at Zeckendorf.

HAND-ATTACK (on paper, before any engine code).
  - Necessity in (5) over Z: as r runs over 0..m - 1 the one-step
    difference floor((r + M)/m) - floor(r/m) takes the value
    floor(M/m) and, when m does not divide M, also floor(M/m) + 1. Two
    consecutive integers are never both divisible by N = M_t >= 2, so
    m | M is forced, and then the difference is M/m, divisible by N iff
    m N | M. Inputs agreeing at depth t + c differ by k M, a chain of k
    one-steps, so one-step pairs decide. The criterion is proved over Z.
  - Over F_q[x] the one-step argument does NOT transfer: division by m
    is F_q-linear, so the condition is that floor(kM/m) lies in (N)
    for EVERY polynomial k, and the pairs (n, n + kM) are not chains of
    +M steps. Sufficiency stands as written; necessity is not proved
    here, so the brute pair search over all polynomials below a degree
    bound is necessity's only evidence and the tier is a rule at that
    scope.
  - Half-open tiles: at leading base 10, y -> 2y maps vertices to
    vertices, and the image [2a, 2a + 2h) of a depth-(t + 1) tile has
    endpoints on the grid of step 2h, which contains the depth-t
    vertices; nothing lies strictly inside, so c = 1 suffices. y -> 3y
    fails at every c, since 3 does not divide 10^c.
  - P-W as first written listed sqrt(3) as emitting; 3 is a vertex, so
    it freezes. Corrected here, before the run.

PREDICTIONS (frozen before any engine code).
  P-L  At trailing base 10, n -> 7n reads at c = 0 and floor(n/4)
       needs c = 2 (4 | 10^2, 4 does not divide 10), at every depth
       scanned.
  P-B  (the new control) Every scaling reads at bounded lookahead at
       both non-archimedean arms: at the 3-adic numeration y -> 2y and
       y -> y/2 read at c = 0; at the 1/x-adic numeration of F_2((1/x))
       multiplication and division by u = x + 1 and u = x^2 + x + 1
       read at c = 0 after the degree shift, exhaustively over all
       inputs of the scanned length. At leading base 10 (R), y -> 3y
       needs lookahead >= k on the input prefix 0.33...3 (k threes)
       for every k scanned, while y -> 2y reads at c <= 1 everywhere
       scanned (the positive control on the wall detector).
  P-W  At leading base 10, y -> y^2 freezes emission at y = sqrt(0.2),
       sqrt(0.5), sqrt(2), sqrt(3) (images 0.2, 0.5, 2, 3 are
       vertices) and emits without bound at y = sqrt(1/3), sqrt(1/7)
       (images 1/3 and 1/7 are in no Z[1/10]).
  P-M  c_min(D, t) = t - 1 exactly at t = 1..10 at base 2.
  P-R  The chain criterion (5) agrees with a brute pair search at
       every (chain, m, t, c) scanned: bases 10 and 12, m = 2..12; the
       primorial chain, m = 2..30, t = 1..4; F_2[x] at bases x and
       x(x + 1), every m of degree <= 3.
  P-X  (added before its engine, after the others ran) The criterion in
       (5) sorts floor(n/m) into all three classes by the chain alone:
       readable at depth t iff the chain absorbs m past t, Lipschitz
       iff the least such lookahead is bounded, MIDDLE iff it is finite
       at every depth and unbounded, DISCONTINUOUS iff some depth never
       absorbs. On the sparse chain with radix 2 at the indices t that
       are powers of two and radix 3 elsewhere, floor(n/2) and
       floor(n/4) are MIDDLE, with c_min(n//2, t) = 2^(floor(log2 t) + 1)
       - t, floor(n/3) is Lipschitz at c <= 2, and floor(n/5) is
       discontinuous, over t = 1..40. So an empty arithmetic middle is a
       fact about fixed-radix chains, not about rings.
  P-C  At d = 2..6 the doubled comb's low digits take exactly d
       patterns over K, with period d(d + 1) in K, inputs agreeing to
       exactly K + d + 1 and doubles differing at a digit <= d - 2.

FINDINGS (entered after the run; prints copied from it).
  - The first run failed one positive control: floor(n/3) at base 10
    "read" at c = 4, 3, 2 at t = 1, 2, 3, because the brute scanned
    n < 30000 and past 10^(t + c) >= 30000 every input tile held one
    sample. The scan now covers four full periods of each input
    modulus; the control then prints [None, None, None]. P-X's first
    run failed n//4 on its lookahead ceiling of 80, below the
    c = 128 - t the depths t = 32..40 need; at 200 it passes.
  - P-L holds: 7n at [0, 0, 0], n//2 at [1, 1, 1], n//4 at [2, 2, 2].
  - P-B holds: 1/x-adic multiplication and division by x + 1 and
    x^2 + x + 1 fix output digits 1..j from input digits 1..j at every
    j to 12 (j = 1 and j = 12 check nothing: the key and top digit are
    1, and at 12 the key is the whole input). Its 3-adic arm and both leading base 10 arms hold by
    algebra (multiplication mod 3^j is well defined; 3 (10^k - 1)/3 =
    10^k - 1, so 3y maps the tile 0.3...3 onto [1 - 10^-k,
    1 + 2 10^-k); 2a + 2 <= 10 (floor(2a/10) + 1)) and are argued,
    no longer checked.
  - P-W holds: y^2 emission at input depth 20, 60, 120, 200 is
    [0, 0, 0, 0] at sqrt(0.2) and sqrt(0.5), [-1, -1, -1, -1] at
    sqrt(2) and sqrt(3), [19, 59, 119, 199] at sqrt(1/3) and
    [19, 59, 119, 200] at sqrt(1/7).
  - P-M holds: c_min(D, t) = [0, 1, ..., 9] at t = 1..10.
  - P-R holds: over Z the brute agrees with m M_t | M_(t+c) at
    1142/1142 (chain, m, t, c) at bases 10, 12 and the primorial chain
    (this brute runs the one-step reduction the proof uses, so it
    checks the floor arithmetic, not the reduction); over F_2[x], where
    the brute takes every pair below its degree bound, a check beside
    SETTLED (5)'s proof of necessity, at 168/168. At the primorial chain n//3
    reads only at depth 1 and n//5 at depths 1 and 2; n//4 at none.
  - P-X holds: on the sparse chain n//2 has c_min
    [1, 2, 1, 4, 3, 2, 1, 8, 7, 6, ...], largest 32 over t = 1..40
    and equal to 2^(floor(log2 t) + 1) - t throughout; n//4 is finite
    at t = 1..40, largest 96; n//3 at most 2; n//5 unread at all 40
    depths. Floor division falls in MIDDLE on a ring.
  - P-C holds at d = 2..6: d patterns, period d(d + 1), inputs
    agreeing to exactly K + d + 1, doubles apart at digit d - 2 (0, 1,
    2, 3, 4). At Zeckendorf the successor reads at c = 1 at t = 1..8
    and 2n at no c <= 6 at depths 1 to 3.
  - P-C2 holds: 112/112 doubles at d = 2..8 are the proof's phase
    sets; with the phase index shifted by one, 0/112 match.

SETTLED ON AUDIT (the argument above stays as frozen; these replace it).
  - (1) and (2): ball tiles have Lebesgue number at least delta_t (at
    base b exactly b delta_t), so the fit costs at most ceil(log_b L)
    digits. The overlapping cover's margin is not proved by a Lebesgue
    number, since the next commitment must be a child of the last. The
    ball regime holds for Lipschitz SELF-MAPS of the unit ball with
    ABSOLUTE tiles; read with the leading exponent first (floating
    tiles), a map cancelling leading digits needs unbounded lookahead
    at every place. A wall needs a NON-REDUNDANT numeration of R; an
    overlapping one (signed digits) reads y -> 3y. The archimedean
    price is the redundancy a wall-free numeration of R must carry.
  - (3): f must be increasing for the half-open tiles; a decreasing f
    can wall at a vertex: when B = -B, negation maps a tile [v, v + h)
    of width h onto (-v - h, -v], meeting the tiles on both sides of
    the vertex -v at every depth past -v's own, so it walls at every
    vertex v.
  - (5) over F_q[x]: necessity IS proved. If m does not divide M, write
    M = qm + s, s != 0, and take k = x^(deg m - deg s): floor(kM/m) =
    kq + a, a a nonzero constant, which cannot lie in (M_t). The brute
    search stands as a check, not as the only evidence.
  - (6) is proved at every d >= 2, one induction uniform in d. LEMMA
    0: a 0/1 string with no d consecutive ones is the greedy expansion
    of its value, since such a string on indices < k sums to at most
    q_k - 1 (one of the top d indices is absent; bases q_j - 1 =
    2^j - 1). LEMMA A: 2 q_k = q_(k+1) + q_(k-d) for k >= d, as
    2 q_k - q_(k+1) = q_k - q_(k-1) - ... - q_(k-d+1) = q_(k-d); and
    q_0 + ... + q_(d-1) = q_d. THE PHASES: write K = d + (d + 1) i'
    with i = i' mod d. For i <= d - 2 the digits of 2 T_K are the
    bottom {0, ..., i} and the teeth j = i + 1 mod d with
    d + 1 + i <= j <= K + 1; for i = d - 1 they are the teeth
    j = 0 mod d with d <= j <= K + 1. Base: 2 T_d = q_(d+1) + q_0.
    Step: 2 T_(K+d+1) = 2 T_K + q_(K+d+2) + q_(K+1) by Lemma A. The
    added q_(K+1) doubles the top tooth and each 2 q_j = q_(j+1) +
    q_(j-d) re-doubles the tooth d below, so every tooth moves up one,
    the deposits at j + 1 disjoint from the teeth left; at the bottom
    tooth d + 1 + i the carry moves q_(i+1) down onto the bottom, giving
    {0, ..., i + 1}, and at i = d - 2 the full bottom {0, ..., d - 1}
    consolidates to the tooth q_d; at i = d - 1 the tooth d splits to
    q_(d+1) + q_0. Every result has teeth d apart and its bottom run,
    of length at most d - 1, below a gap, so it is canonical by Lemma
    0. The d bottoms differ pairwise at a digit <= d - 2, so the d
    phase limits are d image points over the one input limit, and x2
    has no continuous extension at any d. The scan P-C is a check on
    this proof; P-C2 checks the stated sets themselves.
  P-C2 (predicted before its code) The greedy digits of 2 T_K equal
       the phase set above exactly, at d = 2..8 and every K = d +
       (d + 1) i' with i' < 3d + 1.
  - P-C's "positive control" 2n at Zeckendorf is the control that the
    scan sees a tear.
  - The QUESTION's "completing to an odometer or a torus translation":
    the d >= 3 completions are totally disconnected, measurably
    conjugate to a torus translation (Berthe, Jolivet and Siegel,
    Uniform Distribution Theory 7, 2012), not equal to one.
  - A wall is bounded emission, not only "no digit"; on a real
    interval every non-redundant numeration by interval tiles has one
    (y -> v + lam (y - y0), v a depth-1 endpoint), and signed binary
    digits read every L-Lipschitz self-map of [-1, 1] at lookahead
    ceil(log2 L) + 1, since an interval of length r/2 inside a tile of
    half-width r lies in one of its three children.

RUN RECORD: 18/18 checks, 2.5 s, peak commit 104 MB under a memory guard.
"""

import math

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}")


# ---------------------------------------------------------------- trailing
def trailing_cmin(f, mod_in, mod_out, t, cmax, reps):
    """Least c <= cmax such that f(n) mod mod_out(t) is fixed by
    n mod mod_in(t + c) over reps full periods of mod_in(t + c), so
    every input tile holds reps members; None if no c works."""
    for c in range(cmax + 1):
        Mi, Mo = mod_in(t + c), mod_out(t)
        seen, ok = {}, True
        for n in range(reps * Mi):
            key, val = n % Mi, f(n) % Mo
            if seen.setdefault(key, val) != val:
                ok = False
                break
        if ok:
            return c
    return None


def section_l():
    print("L  the lemma's ball regime at trailing base 10")
    p = lambda k: 10 ** k
    rows = {}
    for name, f in (("7n", lambda n: 7 * n), ("n//2", lambda n: n // 2),
                    ("n//4", lambda n: n // 4), ("n//3", lambda n: n // 3)):
        rows[name] = [trailing_cmin(f, p, p, t, 3, 4) for t in (1, 2, 3)]
        print(f"     {name:5s} c_min at t = 1, 2, 3: {rows[name]}")
    check("positive control: n//3 reads at no c <= 3 (3 is no unit of "
          "Z[1/10])", rows["n//3"] == [None] * 3)
    check("P-L: 7n at c = 0, n//4 at c = 2, n//2 at c = 1, depths 1 to 3",
          rows["7n"] == [0] * 3 and rows["n//4"] == [2] * 3
          and rows["n//2"] == [1] * 3)


# ---------------------------------------------------------- F_2[x] algebra
def pmul(a, b):
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        b >>= 1
    return r


def pdivmod(a, b):
    q, db = 0, b.bit_length() - 1
    while a and a.bit_length() - 1 >= db:
        s = a.bit_length() - 1 - db
        q ^= 1 << s
        a ^= b << s
    return q, a


def ppow(a, k):
    r = 1
    for _ in range(k):
        r = pmul(r, a)
    return r


def section_b():
    print("B  which place pays for a wall: the 1/x-adic arm")
    # The 3-adic and leading base 10 arms hold by algebra (FINDINGS).
    # 1/x-adic arm over F_2: an input is its N leading digits, top digit 1
    N = 12
    okt = True
    for u in (0b11, 0b111):
        du = u.bit_length() - 1
        oku = True
        for mode in ("mul", "div"):
            for j in range(1, N + 1):
                seen = {}
                for low in range(1 << (N - 1)):
                    X = (1 << (N - 1)) | low
                    if mode == "mul":
                        Y = pmul(X, u)
                    else:
                        Y = pdivmod(X << (du + 1), u)[0]
                    top = Y >> (Y.bit_length() - j)
                    key = X >> (N - j)
                    if seen.setdefault(key, top) != top:
                        oku = False
        okt &= oku
        print(f"     1/x-adic u = {bin(u)}: y*u and y/u, output digits "
              f"1..j fixed by input digits 1..j, j = 1..{N}: {oku}")
    check("P-B 1/x-adic arm: multiplication and division by x + 1 and "
          "x^2 + x + 1 read at c = 0", okt)


# ------------------------------------------------------------------ walls
def leading_emission(num, den, n):
    """Output depth committed by y -> y^2 at leading base 10 on the
    depth-n input tile around sqrt(num/den); -1 is a tile of width 10,
    -2 not even that."""
    Y = math.isqrt(num * 10 ** (2 * n) // den)
    lo, hi = Y * Y, (Y + 1) * (Y + 1)        # units 10^-2n, half-open
    best = -2
    for t in range(-1, 2 * n + 1):
        w = 10 ** (2 * n - t)
        k = lo // w
        if hi <= (k + 1) * w:
            best = t
        else:
            break
    return best


def section_w():
    print("W  the wall criterion at leading base 10, y -> y^2")
    frozen, grows = {}, {}
    for label, num, den in (("sqrt(0.2)", 1, 5), ("sqrt(0.5)", 1, 2),
                            ("sqrt(2)", 2, 1), ("sqrt(3)", 3, 1),
                            ("sqrt(1/3)", 1, 3), ("sqrt(1/7)", 1, 7)):
        e = [leading_emission(num, den, n) for n in (20, 60, 120, 200)]
        print(f"     {label:9s} emission at input depth 20, 60, 120, 200: "
              f"{e}")
        frozen[label] = e == [0] * 4 if num < den else e == [-1] * 4
        grows[label] = e[-1] >= 190
    check("P-W: sqrt(0.2), sqrt(0.5) freeze at 0, sqrt(2), sqrt(3) at -1",
          all(frozen[k] for k in ("sqrt(0.2)", "sqrt(0.5)", "sqrt(2)",
                                  "sqrt(3)")))
    check("P-W: sqrt(1/3), sqrt(1/7) emit without bound",
          grows["sqrt(1/3)"] and grows["sqrt(1/7)"])


# ----------------------------------------------------------------- middle
def section_m():
    print("M  the middle class: the decimation at base 2")

    def D(n):
        out, t = 0, 0
        while n >> (2 * t):
            out |= ((n >> (2 * t)) & 1) << t
            t += 1
        return out

    p = lambda k: 2 ** k
    got = [trailing_cmin(D, p, p, t, 12, 4) for t in range(1, 11)]
    print(f"     c_min(D, t), t = 1..10: {got}")
    check("P-M: c_min(D, t) = t - 1", got == list(range(10)))


# ----------------------------------------------------------------- chains
def primorial(t):
    ps, x, n = [], 1, 2
    while len(ps) < t:
        if all(n % p for p in ps):
            ps.append(n)
            x *= n
        n += 1
    return x


def int_brute(m, N, M):
    """Division by m keeps its quotient mod N across every one-step
    pair (n, n + M), n over three periods of m?"""
    return all((n + M) // m % N == n // m % N for n in range(3 * m))


def poly_brute(m, N, M):
    """Over F_2[x]: all n below degree deg M + deg m + 2, grouped by
    n mod M, keep n div m mod N?"""
    D = (M.bit_length() - 1) + (m.bit_length() - 1) + 2
    seen = {}
    for n in range(1 << D):
        key = pdivmod(n, M)[1]
        val = pdivmod(pdivmod(n, m)[0], N)[1]
        if seen.setdefault(key, val) != val:
            return False
    return True


def section_r():
    print("R  the division criterion on a divisor chain")
    agree = total = 0
    for mods, ms, ts, cs in (
            (lambda k: 10 ** k, range(2, 13), (1, 2, 3), range(5)),
            (lambda k: 12 ** k, range(2, 13), (1, 2, 3), range(5)),
            (primorial, range(2, 31), (1, 2, 3, 4), range(7))):
        for m in ms:
            for t in ts:
                for c in cs:
                    N, M = mods(t), mods(t + c)
                    total += 1
                    agree += int_brute(m, N, M) == (M % (m * N) == 0)
    print(f"     Z chains (bases 10, 12, primorial): brute agrees with "
          f"m M_t | M_(t+c) at {agree}/{total} (chain, m, t, c)")
    check("P-R over Z: the criterion matches the brute pair search",
          agree == total)
    reads = {m: [t for t in range(1, 6)
                 if any(primorial(t + c) % (m * primorial(t)) == 0
                        for c in range(8))] for m in (3, 5, 15, 35, 4)}
    print(f"     primorial chain, depths t <= 5 at which n//m reads at "
          f"some c <= 7: {reads}")
    check("P-R primorial: n//3 reads at depth 1, n//5 at 1 and 2, n//4 "
          "at none, t <= 5",
          reads[3] == [1] and reads[5] == [1, 2] and reads[4] == [])
    agree = total = 0
    for g in (0b10, 0b110):
        for m in range(2, 16):
            for t in (1, 2):
                for c in (0, 1, 2):
                    N, M = ppow(g, t), ppow(g, t + c)
                    total += 1
                    crit = pdivmod(M, pmul(m, N))[1] == 0
                    agree += poly_brute(m, N, M) == crit
    print(f"     F_2[x] at bases x and x^2 + x: brute agrees with "
          f"m M_t | M_(t+c) at {agree}/{total} (base, m, t, c)")
    check("P-R over F_2[x]: the criterion matches the brute search",
          agree == total)


def section_x():
    print("X  the three classes on one sparse chain")
    radix = lambda t: 2 if t & (t - 1) == 0 else 3
    M = [1]
    for t in range(1, 260):
        M.append(M[-1] * radix(t))
    cls = {}
    for m in (2, 3, 4, 5):
        cs = []
        for t in range(1, 41):
            c = next((c for c in range(0, 200)
                      if int_brute(m, M[t], M[t + c])), None)
            cs.append(c)
        cls[m] = cs
        seen = [x for x in cs if x is not None]
        top = max(seen) if seen else None
        print(f"     n//{m}: c_min at t = 1..10 {cs[:10]}, largest over "
              f"t = 1..40 {top}, unread depths {cs.count(None)}")
    want2 = [2 ** (t.bit_length()) - t for t in range(1, 41)]
    check("P-X: n//2 is MIDDLE, c_min = 2^(floor(log2 t) + 1) - t",
          cls[2] == want2 and None not in cls[2])
    check("P-X: n//4 is finite at t = 1..40, its largest >= 16",
          None not in cls[4] and max(cls[4]) >= 16)
    check("P-X: n//3 is Lipschitz at c <= 2",
          None not in cls[3] and max(cls[3]) <= 2)
    check("P-X: n//5 reads at no depth", cls[5] == [None] * 40)


# ------------------------------------------------------------------ combs
def greedy(n, q):
    digs = set()
    for k in range(len(q) - 1, -1, -1):
        if q[k] <= n:
            digs.add(k)
            n -= q[k]
    assert n == 0
    return digs


def first_diff(a, b):
    d = a ^ b
    return min(d) if d else None


def section_c():
    print("C  the comb: x2 against the d-bonacci numerations")
    allok = True
    for d in range(2, 7):
        per = d * (d + 1)
        Ks = [d + (d + 1) * i for i in range(3 * d + 1)]
        q = [2 ** j for j in range(d)]
        while len(q) < Ks[-1] + 2 * d + 4:
            q.append(sum(q[-d:]))
        T = {K: sum(q[j] for j in range(d, K + 1, d + 1)) for K in Ks}
        pats = {K: frozenset(x for x in greedy(2 * T[K], q) if x < d)
                for K in Ks}
        npat = len(set(pats.values()))
        periodic = all(pats[K] == pats[K + per] for K in Ks
                       if K + per in pats)
        pairs = [K for K in Ks if K + d + 1 in T]
        agree = all(first_diff(greedy(T[K], q), greedy(T[K + d + 1], q))
                    == K + d + 1 for K in pairs)
        low = max(first_diff(greedy(2 * T[K], q),
                             greedy(2 * T[K + d + 1], q)) for K in pairs)
        ok = npat == d and periodic and agree and low <= d - 2
        allok &= ok
        print(f"     d = {d}: patterns {npat}, period d(d + 1) = {per} "
              f"{periodic}, inputs agree to K+d+1 {agree}, doubles first "
              f"apart at a digit <= {low}")
    check("P-C: d patterns, period d(d + 1), agreement K + d + 1, "
          "doubles apart at a digit <= d - 2, d = 2..6", allok)
    # the proof's phase sets, read against greedy extraction
    def phase_set(d, i, K):
        if i <= d - 2:
            return set(range(i + 1)) | {j for j in range(d + 1 + i, K + 2)
                                        if j % d == (i + 1) % d}
        return {j for j in range(d, K + 2) if j % d == 0}

    miss = cells = shifted = 0
    for d in range(2, 9):
        Ks = [d + (d + 1) * i for i in range(3 * d + 1)]
        q = [2 ** j for j in range(d)]
        while len(q) < Ks[-1] + 2 * d + 4:
            q.append(sum(q[-d:]))
        for n, K in enumerate(Ks):
            T = sum(q[j] for j in range(d, K + 1, d + 1))
            got = greedy(2 * T, q)
            cells += 1
            miss += got != phase_set(d, n % d, K)
            shifted += got == phase_set(d, (n + 1) % d, K)
    print(f"     phase sets: {cells - miss}/{cells} doubles match the proof; "
          f"with the phase index shifted by one, {shifted}/{cells}")
    check("P-C2: the proof's phase set is 2 T_K's digits, d = 2..8",
          miss == 0 and cells > 0)
    check("negative control: the phase sets shifted by one match no double",
          shifted == 0)
    # the successor reads at Zeckendorf; x2 is the positive control
    q = [1, 2]
    while q[-1] < 30000:
        q.append(q[-1] + q[-2])
    lim = q[-1]
    masks = [sum(1 << k for k in greedy(n, q)) for n in range(2 * lim)]

    def zc(f, t):
        for c in range(7):
            seen, ok = {}, True
            for n in range(lim):
                key = masks[n] & ((1 << (t + c)) - 1)
                val = masks[f(n)] & ((1 << t) - 1)
                if seen.setdefault(key, val) != val:
                    ok = False
                    break
            if ok:
                return c
        return None

    inc = [zc(lambda n: n + 1, t) for t in range(1, 9)]
    dbl = [zc(lambda n: 2 * n, t) for t in (1, 2, 3)]
    print(f"     Zeckendorf c_min: n + 1 at t = 1..8 {inc}; 2n at "
          f"t = 1..3 {dbl}")
    check("positive control: 2n reads at no c <= 6 at Zeckendorf, "
          "depths 1 to 3",
          dbl == [None] * 3)
    check("the successor reads at c = 1 at every scanned depth",
          inc == [1] * 8)


def main():
    section_l()
    section_b()
    section_w()
    section_m()
    section_r()
    section_x()
    section_c()
    print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
    raise SystemExit(0 if all(CHECKS) else 1)


if __name__ == "__main__":
    main()