""" flush.py -- a redundant output alphabet on the trailing Ostrowski numeration: which maps a bottom-up reader then computes, and what reading the integers costs over reading their completion. QUESTION. Fix an irrational alpha = [0; a_1, a_2, ...] with denominators q_k, numerators p_k and remainders theta_k = q_k alpha - p_k (theta_(-1) = -1), which alternate in sign and shrink. The INPUT is the greedy Ostrowski string of n (ostrowski.py). The OUTPUT alphabet is widened: digit e_k may run to a_(k+1) + s (position 0 to a_1 - 1 + s_0, with s_0 <= s + 1) and the below-a-cap rule is dropped, so an integer has several output strings. A reader at lookahead c writes e_t having seen d_0 .. d_(t+c). Under the legal output, n -> m n walls on the circle and floor(n/m) is no continuous circle map at all (ostrowski.py). Which of the two does redundancy cure? And a reader that must write a FINITE string equal to m n (the INTEGER reader) against one that need only write an infinite string coding the circle point m x (the COMPLETION reader): what separates them? THE ARGUMENT (written before this script). (1) THE RANGES. The real star of a string is sum e_k theta_k, a REAL: two strings of one integer can differ in it by an integer. The tails from level t fill the interval T_t between -sum over the negative theta_k of (cap_k)|theta_k| and the same over the positive ones, and by a_(k+1) theta_k = theta_(k+1) - theta_(k-1) its length is |theta_(t-1)| + |theta_t| + s S_t, S_t = sum_(k>=t) |theta_k| (level 0: 1 + E, E = s_0 alpha + s S_1). The TAIL LEMMA S_t <= |theta_(t-1)| + |theta_t| follows from |theta_(k-1)| >= |theta_k| + |theta_(k+1)|. The members e theta_t + T_(t+1), e = 0 .. cap_t, cover T_t, consecutive ones overlapping by ov_t = |theta_(t+1)| + s S_(t+1). (2) THE TEAR AT E = 0. At s = s_0 = 0, T_0 = [-alpha, 1 - alpha] exactly, so every string of N has as star the representative of N alpha mod 1 in (-alpha, 1 - alpha). The least string (0, a_2, 0, a_4, ...) has star -alpha, the greatest (a_1 - 1, 0, a_3, 0, ...) has 1 - alpha, and star minus -alpha is a sum of non-negative terms (e_k - e^min_k) theta_k, so a string within eta of -alpha agrees with the least string wherever |theta_k| > eta, likewise at the top. They part at position t_0 - 1. The integers of any input tile about the non-cut (1 - alpha)/m have images on both sides of the cut -alpha, so x m commits no output tile past depth t_0 - 1 there, at any lookahead: dropping the rule alone buys nothing. (3) THE COMPLETION READER AT E > 0. Keep the interval J_t of targets the unseen input still allows, M + m (seen star + I) - sum_(k 0 since |theta_(k+2)| < |theta_k| / 2. This is the signed-digit cure of the reading lemma: a cover whose children overlap by a positive amount, on the circle. (4) THE FLOORS DO NOT FOLLOW. A depth-t output cylinder holds stars in an interval of length |T_t|. The integers of any input tile about a non-cut x have floor(n/m) alpha accumulating at m points 1/m apart (ostrowski.py, the residue section), so once |T_t| < 1/m no depth-t output tile holds them: floor division commits nothing from that depth on, anywhere, at any s. (5) THE GAME. Write the residual H_t = m sum_(k<=t) d_k q_k + omega - sum_(k 0 at the rate of the box times |theta_(t-1)|: the output codes m x + M, a completion reader. A completion reader's own lift gives a true branch, inside the box by (5), so it plays safe. So tracking the lifts costs nothing, the width of the box is irrelevant above (5)'s floor, and c_int - c_comp = c_int - c_saf is the price of the flush alone. (7) THE FLUSH FLOOR. If s >= (m - 1) a_(k+1) at every k >= 1, the digitwise reader e_0 = m d_0 mod a_1, e_1 = m d_1 + floor(m d_0 / a_1), e_k = m d_k fits the caps (d_0 >= 1 forces d_1 <= a_2 - 1), whatever s_0: c_int = 0. If (m - 1) a_(k+1) > s and m a_(k+1) < q_(k-1) for infinitely many k, no integer reader has c <= 1: a reader flushed on n writes the same prefix on n' = n + a_(k+1) q_k (k deep, a zero below it) through position k - c - 1, so it owes exactly m a_(k+1) q_k, from level k - c >= k - 1. Writing q_(k+j) = U_j q_k + V_j q_(k-1) with V_j >= 1, a string of value m a_(k+1) q_k from level k - 1 has q_k | Y, Y = e_(k-1) + sum e_(k+j) V_j, and Y >= q_k would force m a_(k+1) >= q_(k-1); so Y = 0 and the only string is e_k = m a_(k+1), over its cap a_(k+1) + s. So c_int is 0 or at least 2, never 1, at every periodic alpha. (8) THE UNIVERSAL READER. The step is labelled by the local quotient only, so over the alphabet {1, .., A} the game with the OPPONENT choosing each quotient is ONE finite game; a win is a reader that sees the quotients through a_(t+c+1) and nothing else of alpha, correct at every alpha with quotients <= A. (9) THE OWED INTEGER (added later). N_t = m sum_(k<=t+c) d_k q_k + omega - sum_(k 0, so the branches left are (0, 0), alpha irrational. Conversely N_t is the value of what the reader writes from t on, >= 0. (b) At a periodic alpha the sign is a function of the state: with theta'_k = q_k alpha' - p_k < 0 (alpha' the conjugate) and zeta'_t = theta'_t/theta'_(t-1) = a_t + 1/zeta'_(t-1) > 1, by t mod p, a branch's TENTATIVE CONJUGATE u~ = G zeta'_t + H obeys N (alpha - alpha') = sigma~ - u~ theta'_(t-1), so u~ >= 0 is N >= 1, or N = 0 with sigma~ <= 0, once |sigma~| < 1 on the box. A step sends u~ to u~/zeta'_t - e plus a non-negative input term, so under zero input u~ < 0 persists and a winner's states all hold a branch with u~ >= 0; conversely, inside the safety game's set on such states, by Koenig a chain of branches with u~ >= 0 runs on under zero input, u~ shrinking by zeta'_min over finitely many values to 0, which is (0, 0) with nothing pending. So c_int is the least lookahead of ONE safety game, and inside its set every safe move flushes. Over a quotient alphabet zeta' is not known to the state, (a) holds per play, and the engine keeps the attractor of (5). (10) THE CONE (added later). Write N_t = K q_(t+1) + L q_t and zeta_k = |theta_k/theta_(k-1)|. At (s, s_0) = (0, 1) every cap is a_(t+1), T_t over theta_t is [-1, a_(t+1) + zeta_(t+1)], and the member e holds J_t iff e is in [j+ - zeta_(t+1), j- + 1]; J_t over theta_t is L - K zeta_(t+1) + I, the ends of I of opposite signs. A step sends (K, L) to (L - e, K - a_(t+2)(L - e)), so the cone K, L >= 0 holds at t + 1 iff L - floor(K/a_(t+2)) <= e <= L, and at K >= 0 every integer of the window lies there: its top is at most L, its bottom at least L - floor(K/a_(t+2)) since (K + 1) zeta_(t+1) < floor(K/a_(t+2)) + 1. x_0 = N_0 - K_0/alpha lies strictly inside J_0, so inside (-1, 1/alpha): K_0 >= 0, and then L_0 >= 0 from x_0 = L_0 - K_0 zeta_1 > -1. So every overlap reader at the (0, 1) windows never owes a negative integer and, by (9a) with no box (the star held in T_t), ends: c_int <= c_ov(0, 1) wherever s_0 >= 1, at every irrational alpha, and c_ov(0, 1) <= 2 ceil(log2 m) + 2 by |theta_(k+2)| < |theta_k|/2. (11) THE SEAM (added later). At s_0 = 0, s >= 1 the level-0 window at the (0, 0) caps, [-1, a_1 - 1 + zeta_1] over alpha, has length 1/alpha, the lift's shift, so J_0 lies in one lift of it or holds its seam -1. Inside: the s = 0 reader from level 0 (the cone lemma never used position 0's cap). Holding -1, |x_0 + 1| <= w_0/alpha: write e_0 = 0 and e_1 = a_2 + 1 (the one use of s = 1), then the s = 0 reader from level 2. With sigma = x_0 + 1, x_1 = a_2 + zeta_2 - sigma/zeta_1 and x_2 = a_3 + zeta_3 - 1 + sigma/(zeta_1 zeta_2), so J_2 lies in [-1, a_3 + zeta_3] once w_0/alpha < zeta_1 zeta_2, that is w_0 < |theta_2|. The cone: M = N_0 + 1 has star sigma, and an integer M > 0 with |star| < 1 over theta_j has K >= 1 at level j (K = 0 gives |L| < 1; K <= -1 gives L >= a_(j+1), star > 1); the two moves leave K_1(M) - 1 and K_2(M) - 1, both >= 0, and L_2 >= 0 as x_2 > -1. So the seam reader at c_sr, the least c with w_0 < |theta_2| and w_t <= |theta_(t+1)| at t >= 1, is an integer reader at (1, 0), hence at every (s, 0) with s >= 1, and c_sr <= 2 ceil(log2 m) + 3. Equality w_0 = |theta_2| never occurs: m >= 2 would divide the coprime q_2 and p_2. (12) THE CYLINDER BOUND (added later). Fix t >= 0 with |T_(t+1)| < 1 and the inputs with d_0 .. d_(t+c) all 0: their stars are dense in I_j, j = t + c + 1, of length |theta_(t+c)| + |theta_(t+c+1)|, and over them a reader at lookahead c has written one e_0 .. e_t. A completion reader, or an integer reader of m n + omega (n = 0 aside), puts each output star m x + omega alpha + M, M an integer, in one translate of T_(t+1); for each M the x allowed form a closed interval of length |T_(t+1)|/m < 1/m, the M's disjoint translates by 1/m, and a dense subset of I_j in finitely many of them puts I_j in one. So m |I_j| <= |T_(t+1)|: c_lo, the least c with w_t <= |T_(t+1)| at every t with |T_(t+1)| < 1, bounds c_comp and c_int below at every irrational alpha, s_0 never entering. Upward: |T_L| falls with L, |T_(t+3)| <= ov_t as |theta_(t+1)| >= |theta_(t+2)| + |theta_(t+3)|, |T_3| < E wherever E > 0, and w_t(c + K) = w_(t+K)(c); so c_ov <= c_lo + max(2, t_1), t_1 the least t with |T_(t+1)| < 1, and |T_(t+1)| <= |theta_(t-1)| + 2s|theta_t| < (1 + 2s) 2^-floor(t/2) at t >= 1 gives t_1 <= max(1, 2 ceil(log2(2s + 1))). At a purely periodic alpha w_t/|T_(t+1)| has the period, so the bar holds at every t and the gap is at most 2, as wherever |T_3| < 1. Golden: c_lo is the least c with m phi^-c <= 1 + s, c_ov the least with m phi^-c <= s + min(phi^-2, s_0/phi). (13) THE PINNED ZERO CYLINDER (added later). At s = 0, T_L = I_L for L >= 1, its members e theta_L + I_(L+1), e = 0 .. a_(L+1). Fix t with |I_(t+1)| < 1 (t = 0 at a_1 = 1 aside, where |T_1| = 1), j = t + c + 1. By (12) the lift M is one integer over I_j, and a reader of x m (completion, or integers at omega = 0) writes there one e_0 .. e_t, sigma_t = N alpha - P, N = sum e_k q_k in 0 .. q_(t+1) + q_t - 1 at s = 0, s_0 = 1; so delta = M + P - N alpha has delta + m I_j inside I_(t+1), and delta is interior to it as 0 is interior to I_j. For 0 < N < q_(t+1), |N alpha - K| >= |theta_t|; for N = q_(t+1) + N', N' < q_t, K - N alpha is -theta_ (t+1) plus a point at distance 0 or >= |theta_(t-1)| = a_(t+1) |theta_t| + |theta_(t+1)| or 1: never interior. So N = 0, M = 0: the zero cylinder is written as zeros through level t at lift 0, and m I_j lies inside I_(t+1) (ONE LEVEL: R(t, c), R(t + 1, c) at c even, R(t, c + 1), R(t + 1, c - 1) at c odd, R(k, g) being m |theta_(k+g)| <= |theta_k|). TWO LEVELS: over C_0 = I_(j+1) and C_d = hull{(d - 1) theta_j - theta_(j+1), d theta_j - theta_(j+1)}, d = 1 .. a_(j+1), the reader has written e_(t+1), so m C_d lies in one member of T_(t+1). Z(c), both levels at every t, bars every reader at c; c_lo2 = 1 + the largest c with Z(c) failing. c_lo <= c_lo2, as m|I_j| <= |I_(t+1)| is c_lo's bar, and c_lo2 <= min(c_comp, c_int); by (6), c_lo2 <= c_saf wherever c_saf is defined. Z(c) holds once 2^floor((c - 1)/2) >= m, as R(k, g) does once 2^floor(g/2) >= m. At a constant quotient a, R reads m r^g <= 1, r the ratio, so the one-level bar is c_lo rounded up to even. The second level adds to the one-level bars at t and t + 1 only the SEAM BAR at c even: each overlap zone of T_(t+1) past the first (member 1 reaches 0) that the m C_d, d >= 1, straddle holds a seam between two of them. At a = 1 there is one zone, so golden's c_lo2 is c_lo rounded up to even. With c_int <= c_ov(0, 1) <= c_lo + 2, c_int is c_lo2 + 0..2, and + 0..1 wherever c_lo2 > c_lo. (14) THE PINNED LIMIT (added later). Read (13)'s subtree L levels: at i = 0 .. L - 1 the target m X_i lies in the committed window W_i, X_0 = I_j, W_0 = I_(t+1); at i >= 1 the opponent picks d_(j+i-1), then the reader e_(t+i), X_i = sum_(k=j)^(j+i-1) d_k theta_k + R, W_i = sum_(k=t+1)^(t+i) e_k theta_k + I_(t+i+1), R = I_(j+i) after a digit 0 and R' = hull(-theta_(j+i), -theta_(j+i-1) - theta_(j+i)) after a digit >= 1. c_L, 1 + the largest c at which some pin level fails, is non-decreasing in L, c_1 the one-level bar and c_2 = c_lo2. Its limit is one membership: c_inf, 1 + the largest c at which some PINNED STATE P_t (the branch (0, 0), the quotients a_(t+1) .. a_(t+c+1), the pending digits 0) is outside the safety game's set W. A strategy surviving every L exists by Koenig (finite choices on both sides) and codes m x exactly on the subtree, so its lift-0 branch is a true branch and the box (5) keeps it: P_t wins. A safe play from P_t keeps a lineage, which by (6) codes m x + M, M = 0; by (13) no move at that lift but e = 0 is in a safe play, so its output star lies in every W_i. Every c from c_comp on passes every L, so lim c_L = c_inf, reached at a finite L. c_lo2 <= c_inf <= c_comp = c_saf: by (12) and (13) every completion reader writes the zero cylinder at lift 0, so its lift-0 branch survives from P_t. c_zero, the same read off the unmodified game's initial state with d_0 .. d_c all 0, equals c_inf. At a purely periodic alpha P_p plays as that state with the lift 0 alone (the quotients and the source state repeat, and position 0's cap a_1 - 1 + s_0 is a_1 at s_0 = 1; only the position-0 flag differs), so P_p winning makes the zero state, its branches a superset, win; and a winning play from the zero state, the opponent playing zeros, writes zeros through t by (13), reaching a state that holds P_t's (0, 0), whose survivor has lift 0 by (12) and (13) again, so that strategy followed from P_t never empties it (strategy transfer; monotonicity runs the other way). PREDICTIONS (frozen before the engine ran). C1 CONTROLS, run first. (a) At every alpha the range T_0 has length 1 + E and each overlap is ov_t as (1) says, the tail lemma holds at every level read. (b) The legal output (rule kept, s = s_0 = 0) through the game: the identity at 0, n + 1 at 1, x 2 and x 3 at no c <= LOOKCAP at all six periodic alphas (ostrowski.py's theorems); with the rule dropped, n + 1 at 0. (c) Every winning integer-game strategy of the grid and the band writes m n + omega under the caps and flushes for every n < N_CHECK, 0 bad (the legal output's are not certified). (d) The grid's c_int agrees at every cell with the table of an earlier, independent engine (lattice points of the quadratic field of alpha, a box derived otherwise), EARLIER below. P1 THE TEAR. Every string of every N < N_TEAR at s = s_0 = 0 has star the representative of N alpha mod 1; every string within eta of an end agrees with that end's extreme string where |theta_k| > eta; the extremes part at t_0 - 1. The game's (0, 0) column: x m reads at no c <= LOOKCAP. Kill: one string off. P2 THE COMPLETION READER. At every alpha (the six periodic ones, e - 2, and the band alphas) and every grid cell with E > 0, the overlap reader at c_ov never fails to find a member over N_PLAY random inputs to depth DEPTH, and |its star - (m x + M)| is at most |T_DEPTH|. c_ov printed at the grid's cells. Kill: a failure. P3 THE FLOORS. For m = 2, 3 and s = s_0 = 0..3, at the first depth t* with |T_t*| < 1/m, every input tile at depth t* + c (c = 0..3) holding at least 12 integers below N_FLOOR has a circular hull of floor(n/m) alpha longer than |T_t*|. Kill: a tile whose hull fits. P4 THE FLUSH FLOOR. (a) The digitwise reader is correct on n < N_CHECK at every cell with s >= (m - 1) a_max, s_0 = 0 included. (b) At one k of every phase, the first k >= 2 with m a_(k+1) < q_(k-1), value m a_(k+1) q_k has exactly one string from level k - 1, of any digit sizes. (c) Over the grid, c_int is 0 exactly where s >= (m - 1) a_max and at least 2 elsewhere. Kill: a printed 1, or a 0 below the line. P5 THE COMPLETION READER IS THE SAFETY GAME. (a) The overlap reader's true branch, tracked in frame coordinates, never leaves the box at any cell of P2: the largest |g|/B_g and |h|/B_h printed beside it. (b) c_saf <= c_ov at every cell. (c) --full: c_saf at twice the box equals c_saf at the box at a sample of cells. (d) The band cells [4] x 2 at s = s_0 = 3, [5] x 2 at 3, [4] x 3 at 5 and bronze x 3 at 5: c_ov = 1, so c_comp <= 1, and c_int >= 2 by P4: a strict flush price at each (the check asks c_int = 2). Kill: c_saf above c_ov, a branch out of the box, or c_int <= 1 at a band cell. P6 THE UNIVERSAL READER. {1, 2}: x 2 at (1, 1) wins at 2 and not at 1 (the default run). --full: {1, 2, 3} x 2 at (1, 1) at 2; {1, 2} x 3 at (1, 1) at exactly 3 and x 3 at (2, 2) at 2; every win certified at 12 random alphas over the alphabet and its constant ones; the flushing lineages of a win solved at twice the box stay inside the box ({1, 2}, x 2); every primitive {1, 2}-necklace of period <= 8 reads x 3 at (1, 1) at c_int = 2, at every rotation. Not predicted: whether a periodic member reaches the class's 3. THE PIN (added later, a corollary): a win at 2 bounds c_int by 2 at every alpha of its class, and the flush floor bounds it below by 2 wherever (m - 1) a > s for a quotient a that recurs, since m a_(k+1) < q_(k-1) then holds at every deep k; so the grid's c_int is 2 at each grid alpha of a class won at 2 with such a quotient. P7 THE OWED INTEGER (frozen with (9), in an earlier script). At every grid cell and every c from 0 to c_int (to LOOKCAP where none), the safety game's set on the states with a branch of u~ >= 0 equals the integer game's; every flushed state has a branch with u~ = 0, and over the branches of tentative pair other than (0, 0) the least |u~| stays above 1e-7. CONTROL: the real side's ratio |theta_t/theta_(t-1)| in place of zeta' must move the set at some cell. Kill: a cell off, or a margin below 1e-7. P8 THE CONE (frozen with (10)). At the grid's alphas, e - 2 and (full) one random {1, 2, 3} alpha, the reader of (10), exact, least lift, at the (0, 1) windows and caps: (a) at c from c_ov(0, 1) (full: to + 2), least and greatest member, omega = 0 and m, every n < N_CHECK and the random greedy strings read to m n + omega and end, with no step of K < 0 or L < 0; (b) c_ov(0, 1) <= 2 ceil(log2 m) + 2 at every alpha and m, c_int <= c_ov(0, 1) at every grid cell. CONTROL, the known answer, read first: the reader at c_int - 1, where c_int >= 1, fails at every cell. CONTROL, one variable, the windows: the same reader, least member, on the (1, 1) windows and caps at that cell's c_ov(1, 1) must fail at some cell where c_ov(1, 1) >= c_int(1, 1) (predicted: at K = 0 the member L + 1 is allowed there). Kill: a failure or a negative coordinate in (a), or (b) off. (c) THE SEAM (frozen with (11), in an earlier script). The seam reader at the (0, 0) windows and the (1, 0) caps, at the same alphas and inputs, c_sr (full: and c_sr + 1), both members, omega = 0 and m: no failure, no step of K < 0 or L < 0, the seam taken at every cell; c_sr <= 2 ceil(log2 m) + 3, c_int(1, 0) <= c_sr at every grid cell. CONTROL, the known answer, read first: the seam reader at c_int(1, 0) - 1, where c_int(1, 0) >= 1, fails at every cell. PLANT: the seam's bar loosened to w_0 <= |theta_1| (c_pl, the s = 0 bars alone) fails at some cell where c_pl < c_sr. Kill: a failure or a negative coordinate, a cell with the seam never taken, or a bound off. P9 THE CYLINDER BOUND (frozen with (12), in an earlier script; the gap bound, its t_1 clause and the wall settled after that script's first run: see the run record). c_lo's bars read from above, so that an exact tie passes, and c_ov's both ways, which must give one c_ov at every cell but the golden controls. CONTROLS, read first: c_lo and c_ov at golden x 2 .. x 9 equal (12)'s closed forms; the bar ov_t (too strict) puts c_lo above c_saf at some cell; the bar |T_t| (too lax) gives a gap of 3 at golden s = 0. Kill: c_lo above c_saf or c_int at a finite grid cell; c_ov - c_lo outside 0 .. 2 at a grid cell, or at e - 2 and P8's random alpha, where |T_3| < 1 is printed; a gap above max(2, t_1), or t_1 above its bound, at any cell read. THE WALL: on the family [1 x (N + 1), 10^8, ...], N = 2 .. 7, s the least with |T_N| >= 1, m = 2 .. 4096 in powers of 2, the largest gap is max(2, t_1). (b) THE ZERO CYLINDER (frozen with (13), in an earlier script). Every hull tested from its definition, exactly, over t < 60 at the six periodic alpha (the ratios and quotients repeat), c < 30. CONTROLS, read first: the sub-cylinders tile I_j and the members' hull is I_L; golden x 2 .. x 9 is c_lo rounded up to even; silver x 4 has one-level bar 2 and c_lo2 3, the seam's bite. The pinning: every N < q_(t+1) + q_t enumerated at each level with q_(t+1) + q_t <= NPIN, N = 0 alone strictly inside. Printed beside it: the least c at which Z(c) holds against c_lo2, x 2 .. x 9 at the six alpha. Kill: c_lo2 above c_saf, c_saf above c_int or c_lo above c_lo2 at a grid cell at (0, 1); c_int - c_lo2 above 1 where c_lo2 > c_lo; at e - 2 and P8's random alpha, depth 110, c_lo2 outside c_lo .. c_ov(0, 1). (c) THE PINNED LIMIT (frozen with (14), in an earlier script, at x 2 .. x 5; x 6 .. x 9 after its first run; the grid control and the plant's limit arm added here). At the six alpha at (0, 1), x 2, x 3 (full: x 2 .. x 9), t = 1 .. 2p (the geometry repeats with the period): c_L for L <= 10 (full: 14) read exactly at c up to c_saf + 1; c_inf from the pinned game and c_zero from the unmodified one at c up to c_saf. CONTROLS, read first: c_L at L = 1 and 2 is the one-level bar and c_lo2; c_saf equals the grid's; c_inf = c_saf where c_lo2 = c_saf; at c_saf the pinned states' only winning move is 0. PLANT: R' read as d theta + I_(K+1) moves the L = 2 control at some cell and, at some cell of maps(), the limit. Predicted: c_L stops by L = 8; c_inf = c_saf at every cell (the hypothesis, credence 40%). Kill: K1, c_L or c_inf above c_saf at any cell; K2, lim c_L or c_zero off c_inf at any cell. THE DESIGN. Exact rationals for everything metric (ostrowski.py's Numeration, alpha replaced by a convergent past 10^60). One game engine for every quotient source: a periodic alpha is the source cycling its period, a class is the source offering every letter at every step. The state holds the sorted branches, the pending quotients a_(t+1) .. a_(t+c+1), the source's state, the pending digits, whether the last input digit is 0, whether this is position 0, and whether the last output digit is 0 (read only with the rule kept, but carried always, so every printed state count includes it). Safety is a greatest fixed point; the flush alternates it with the attractor of the flushed states under zero input. The reader picks, among moves keeping every reply winning, one of least rank toward the flush under zero replies: a rank that falls at every zero step, set once per state, not always the least distance. Default: the grid at golden, silver and sqrt(3) - 1 for x 2 and x 3, the band cell [4] x 2, the {1, 2} universal cell; `--full` runs everything above. FINDINGS (entered after the run, from its prints; `--full`). F1 CONTROLS (C1, all green; (a) and (b) run first, (c) and (d) inside the grid). The ranges and overlaps agree with (1) to half the truncation bound at worst over seven alphas and six slacks. The legal output reads the identity at 0, n + 1 at 1, and x 2, x 3 at no c <= 3 at all six periodic alphas; with the rule dropped n + 1 reads at 0. The strategy extracted from every win of the grid and the band is correct on every n < 1000. The grid's c_int agrees with EARLIER at all 144 cells. F2 THE TEAR (P1 lands). 8,321 strings of N < 300 at seven alphas: 0 stars off, 0 disagreements with the extremes; the (0, 0) column reads at no c <= 3 everywhere. F3 THE OVERLAP READER (P2 lands). 36,000 runs to depth 40 at nine alphas, x 2 .. x 5, five slacks: 0 failures, every output star within |T_40| of m x + M. c_ov runs from 0 to 6 over the grid (golden x 5 at (0, 1) is 6). F4 THE FLOORS (P3 lands). 9,063 (tile, m, s, c) tests, m = 2, 3, s = s_0 = 0 .. 3, c = 0 .. 3: none fits; the least hull exceeds |T_t*| by 0.196. F5 THE FLUSH FLOOR (P4 lands). The digitwise reader is correct at every alpha and m = 2 .. 5 at s = (m - 1) a_max, s_0 = 0; the value m a_(k+1) q_k has one string from level k - 1 of any digit sizes at every phase, e_k = m a_(k+1), over its cap a_(k+1) + s when (m - 1) a_(k+1) > s, so there it has no capped string: P4(b) as frozen read "exactly one capped string", which was wrong, and it now reads as the check counts, strings of any digit sizes; over the grid c_int is 0 exactly where s >= (m - 1) a_max and 2 or more elsewhere. c_int - c_saf over the 120 finite cells: 0 at 91, 1 at 28, 2 at one (V1 x 3 at (3, 3), c_saf 0). F6 THE SAFETY GAME (P5 lands). The overlap reader's true branch uses at most 0.92 of B_g and 0.42 of B_h; c_saf <= c_ov at every cell; c_saf is unchanged at twice the box at four cells; at the four band cells c_ov = c_saf = 1 and c_int = 2, strategies 0 bad. F7 THE UNIVERSAL READER (P6 lands). x 2 at (1, 1) reads at exactly 2 over {1, 2} (28,268 states) and {1, 2, 3} (225,747); x 3 at (1, 1) at exactly 3 over {1, 2} (246,554) and x 3 at (2, 2) at 2 (87,131). Every win certified at 14 or 15 members on n < 500, 0 bad; the flushing lineages at twice the box reach (4, 2) against (10, 6). All 472 purely periodic {1, 2} alphas of primitive period <= 8 (every rotation of the 71 words) read x 3 at (1, 1) at 2: no periodic member of the class to that period needs the class's 3. The pin holds at all 11 (class, cell) pairs it prints, 8 distinct grid cells (x 2 at (1, 1): silver, bronze, [1, 2], [1, 1, 1, 2], [2, 1, 3, 1]; x 3 at (2, 2): silver, [1, 2], [1, 1, 1, 2]), each class's members listed per class. F8 THE OWED INTEGER (P7 lands). "cells off: 0 of 144": the two sets agree at all 490 (cell, c) compared, 135 of them non-empty (the 120 winning c, and 15 losing ones that keep states but no initial one); "flushed states without a u~ = 0 branch: 0", the margin 3.837e-02; the first clause holds by construction (a flushed state's (0, 0) branch with nothing pending has u~ = 0 exactly), so the margin is the read. The control moves the set at 116 of 144. The margin's population was narrowed after the first run, which struck only the literal (0, 0) branch with nothing pending and printed 0: a branch whose pending digits cancel it has tentative pair (0, 0), u~ = 0 exactly. F9 THE CONE (P8 lands). "failures at c >= c_ov(0, 1): 0; steps with K < 0 or L < 0: 0" over eight alphas (the grid's six, e - 2, one random {1, 2, 3}), x 2 .. x 5, c from c_ov(0, 1) to + 2, every n < 1000 and 100 random strings of length 60; the known answer "passes at 0 of 24 cells". c_ov(0, 1) is at most 4, 5, 5, 6 for m = 2 .. 5 against the bound 4, 6, 6, 8, met at x 2 by four of the eight alphas; c_int <= c_ov(0, 1) at the 24 grid cells, equal at 18. The control, at the theorem's lookahead, omega = 0 and the least member, on the (1, 1) windows and caps (an integer reader exists there, by the caps): "fails at 27, a negative coordinate at 27 (by the lift at 27, by a member at 14), of 32 cells; n = 0 fails at 27, alone at 13, its lift K_0 = -1 at 27". (c) The seam at c_sr and c_sr + 1: "seam failures at c >= c_sr: 0; steps with K < 0 or L < 0: 0; cells where the seam is never taken: 0 of 32" (64 to 1,904 seam reads a cell, of 8,800); "c_sr above 2 ceil(log2 m) + 3: 0 of 32; c_int(1, 0) above c_sr: 0", c_sr at most 5, 6, 6, 7 for m = 2 .. 5, the bound met at golden x 2 alone, 1 to 5 above c_int(1, 0) at the 24 grid cells; the known answer "passes at 0 of 23 cells" (golden x 2 has c_int(1, 0) = 0); the plant "c_pl < c_sr at 21 cells, fails at 12, its failures {'no member at t = 2': 303}". F10 THE CYLINDER BOUND (P9 lands). Controls: "0 of 40 off"; the strict bar "puts c_lo above c_saf at 27 cells", the lax one "gaps [3, 3, 3, 3]". "c_lo > c_saf at 0 cells, c_lo > c_int at 0"; "c_ov - c_lo over the grid: 0: 31, 1: 67, 2: 22"; "c_saf - c_lo: 0: 54, 1: 56, 2: 10; c_lo = 0 and c_saf = 0 disagree at 0 cells"; "c_int - c_lo at s = 0: 1: 14, 2: 10". "ties (a bar met exactly, missed when summed to top): 6 cells, at s = (m - 1)a, a the constant quotient: 6". e - 2 and the random alpha: "|T_3| < 1 at every slack: yes; c_ov - c_lo 0 to 2". The family: s 1, 3, 6, 11, 19, 32 and t_1 = N, the largest gap N, at c_lo 1 and c_ov N + 1, at x 4, 16, 64, 256, 512, 2048. "gap above max(2, t_1): 0; t_1 above max(1, 2 ceil(log2(2s + 1))): 0; c_ov with its bars read from above moves at 0 of 232 cells". (b) The zero cylinder (P9(b) lands). Controls: "0 faults over the six alpha"; golden "[2, 4, 4, 4, 4, 6, 6, 6]"; silver x 4 "one level 2, two levels 3". The pinning reads N = 0 alone at "[19, 11, 8, 14, 16, 13]" levels; the least passing c differs from c_lo2 at "0 of 48". c_lo / one level / c_lo2 / c_saf / c_int, x 2 .. x 5: golden 2/2/2/3/3 3/4/4/5/5 3/4/4/5/5 4/4/4/6/6 silver 1/2/2/2/2 2/2/2/3/3 2/2/3/3/3 2/2/2/4/4 bronze 1/2/2/2/2 1/2/2/2/2 2/2/2/3/3 2/2/2/3/3 sqrt(3) - 1 2/2/2/3/3 2/2/2/4/4 3/4/4/5/5 3/4/4/5/5 V1 2/2/2/3/3 3/4/4/4/4 3/4/4/5/5 4/4/4/5/5 V2 2/2/2/3/3 2/2/2/4/4 3/4/4/4/4 3/4/4/5/5 "c_int - c_lo2: 0: 6, 1: 14, 2: 4; where c_lo2 > c_lo: 0: 6, 1: 6; where c_lo2 = c_lo: 1: 8, 2: 4; the seam bar moves c_lo2 at ['silver x4']"; c_saf = c_int at all 24. c_lo/c_lo2/c_ov at depth 110, x 2 .. x 5: e - 2 "2/2/4, 3/4/4, 3/4/4, 3/4/4", random "2/2/4, 3/4/5, 3/4/5, 4/4/5". (c) The pinned limit (P9(c) lands, but for one prediction). Controls: c_saf "0 of 24 off", L = 1 and 2 "0, 0 of 48 off", "0 of 12 off", "0 states"; the plant moves the L = 2 control and the limit "at 8 of 48 cells and 1 of 24". "K1: ... 0 cells", "K2: ... 0 disagreements". "c_L stops at L = [1, 2, 3, 4, 5, 6, 7, 9, 10] of 14": the stop by L = 8 failed, the latest stops 9 and 10. "c_inf = c_saf at 48 of 48 cells; at c_saf - 1 every pre-read loses at 48 of 48". c_inf, x 2 .. x 9: golden 3 5 5 6 6 7 7 7, silver 2 3 3 4 4 4 4 4, bronze 2 2 3 3 3 3 3 4, sqrt(3) - 1 3 4 5 5 5 5 5 6, V1 3 4 5 5 6 6 6 6, V2 3 4 4 5 5 5 5 5. Checks that read less than they seem, kept as reads: C1's tail lemma is an equality at golden, so its margin there is the truncation's; C1 reads the overlaps at L < 30 and the lemma at L < 40, and its |T_0| and overlap tests (ov is |T_(L+1)| - |theta_L| by definition) fail only through a slip in Metric's caps, theta or truncation; P1's parting of the extremes fails only at a_2 = 0; P5(c)'s and EARLIER's comparisons pass on None against None, which the prints show; P9(b)'s sub-cylinders share their ends by construction, so only its hull = I_j clause reads the recurrence; P9(c) recomputes c_saf with the grid's own solver, failing only where the grid's search cap cut it short. RUN RECORD. `--full` under a 512 MB watch, its last run below. Two earlier full runs were killed at the ceiling while holding a twice-box game beside the {1, 2, 3} and the x 3 cells; the twice-box lineage check now runs at {1, 2}, x 2 only, and each game is freed before the next. A print of the c_int - c_saf tally was added to the grid after the slate froze. An independent audit then found P6's necklaces read at one rotation each (71 of the 472 alphas) and P1's comparison stopping at a string's own length; both now run whole, and every print above is the whole run's. A later reading found the box's A taken over a_1 .. a_52, past the quotients the track's times 0 .. 40 use (a_1 .. a_41); at e - 2 that inflated B_g, and with A over a_1 .. a_41 the branch's share of B_g is 0.92, first printed as 0.77. The same reading split P6's unflushed reads from its seed mismatches and asserted the (0, 0) column's safety game too. A print of c_ov's range over the grid was added later, and P7 after it, and P8 after that, its control later moved from c_ov(1, 1) to c_ov(0, 1) so that it differs from the reader in the windows and caps alone; the run after: 36/36, 156.6 s, peak 311.5 MB. P8(c) came from a lab script whose verdicts and c_sr matched (c)'s prints (its inputs and random alpha drew from another seed); the run after: 40/40, 167.4 s, peak 312.9 MB. P9 came from a lab script whose prints it matches at every count above but three that are new: the s = 0 tally, the ties' count at s = (m - 1)a and c_ov's both-ways read beyond the grid. That script's first run, its bars summed to top, put c_lo above c_saf and above c_int at six cells each and its golden closed forms off at 4 of 40, every miss a tie, which killed its frozen floor; with the bars re-read from above (hence Metric's reading) the floor and gap-2 kills held, its kill on the family (a largest gap <= 2) did not fire, and its frozen prediction that the gap exceeds 2 and grows with m failed: the gap tracked N, not m. So c_ov <= c_lo + max(2, t_1) was frozen after it, as a second pass, whose first print found t_1 <= 2 ceil(log2(2s + 1)) false at the 20 cells with s = 0 and a_1 = 1 (|T_1| = 1 exactly), the bound becoming max(1, .); the wall's equality, the largest gap max(2, t_1), is that pass's observation. The run after: 48/48, 169.0 s, peak 314.0 MB. A later audit found c_ov read from above only on the grid; the print now covers every cell but the golden controls, its plant (the above-read overlaps tripled) moving c_ov at 32 of the default run's 122 cells and failing the check. The run after: 49/49, 168.2 s, peak 310.3 MB. P9(b) came from a lab script whose prints it matches at every count; that script's plant, the sub-cylinders read by length alone, equals the one-level bar by construction and was dropped. Broken in a scratch copy, the pinning read with its interval closed finds another N at every alpha, and the members cut to member 0 fail four of P9(b)'s checks. The run after: 57/57, 219.6 s, peak 312.3 MB. P9(c) came from a lab script whose prints it matches at every count but the plant's, its x 6 .. x 9 widening a second run there; that script first ran the subtree at every c and t, and was refused at the ceiling, so the engine reads c <= c_saf + 1 and t = 1 .. 2p. Its plant ran at x 2 .. x 5 alone; here it runs the L = 2 control at every cell and the limit at x 2 .. x 5, the limit arm added after an audit found the first port's plant reaching L = 2 alone (64/64, 246.3 s, 346.9 MB). The run after: 64/64, 244.3 s, peak 347.5 MB. """ import os import random import sys import time os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) from ostrowski import Numeration, e_minus_2 # noqa: E402 CHECKS = [] FULL = "--full" in sys.argv # the record run; the default runs small LOOKCAP = 3 N_CHECK = 1000 if FULL else 400 N_TEAR = 300 if FULL else 120 N_FLOOR = 60000 if FULL else 20000 N_PLAY, DEPTH = (200, 40) if FULL else (60, 30) SEED = 20260924 PERIODIC = [("golden [1]", (1,)), ("silver [2]", (2,)), ("bronze [3]", (3,)), ("sqrt(3) - 1 [1, 2]", (1, 2)), ("V1 [1, 1, 1, 2]", (1, 1, 1, 2)), ("V2 [2, 1, 3, 1]", (2, 1, 3, 1))] SLACKS = [(0, 0), (0, 1), (1, 0), (1, 1), (2, 2), (3, 3)] # The integer reader's least lookahead over this grid as an earlier, # independent engine printed it (lattice points of the quadratic field # of alpha, its own box): rows x2..x5, columns SLACKS, None for no c up # to its cap. EARLIER = { "golden [1]": [[None, 3, 0, 0, 0, 0], [None, 5, 2, 2, 0, 0], [None, 5, 3, 3, 2, 0], [None, 6, 3, 3, 2, 2]], "silver [2]": [[None, 2, 2, 2, 0, 0], [None, 3, 2, 2, 2, 2], [None, 3, 3, 2, 2, 2], [None, 4, 3, 3, 2, 2]], "bronze [3]": [[None, 2, 2, 2, 2, 0], [None, 2, 2, 2, 2, 2], [None, 3, 2, 2, 2, 2], [None, 3, 2, 2, 2, 2]], "sqrt(3) - 1 [1, 2]": [[None, 3, 2, 2, 0, 0], [None, 4, 2, 2, 2, 2], [None, 5, 3, 3, 2, 2], [None, 5, 3, 3, 2, 2]], "V1 [1, 1, 1, 2]": [[None, 3, 2, 2, 0, 0], [None, 4, 2, 2, 2, 2], [None, 5, 3, 3, 2, 2], [None, 5, 4, 4, 2, 2]], "V2 [2, 1, 3, 1]": [[None, 3, 2, 2, 2, 0], [None, 4, 2, 2, 2, 2], [None, 4, 3, 3, 2, 2], [None, 5, 3, 3, 2, 2]], } BAND = [("[4]", (4,), 2, 3), ("[5]", (5,), 2, 3), ("[4]", (4,), 3, 5), ("bronze [3]", (3,), 3, 5)] def check(name, ok, detail=""): CHECKS.append(bool(ok)) tag = "ok " if ok else "FAIL" print(f" [{tag}] {name}" + (f" -- {detail}" if detail else "")) def numeration(name, period): reps = -(-200 // len(period)) while True: quots = list(period) * reps try: return Numeration(name, quots) except AssertionError: reps += 1 # ------------------------------------------------------------ the metric class Metric: """theta_k, the level ranges T_L and their overlaps at slack (s, s0), exactly: every real is held as its numerator over the convergent's denominator Q.""" def __init__(self, w, s, s0, top): self.s, self.s0, self.top = s, s0, top self.Q, self.a = w.Q, w.a self.th = [A * w.Q + B * w.P for A, B in (w.theta(k) for k in range(-1, top + 3))] def theta(self, k): return self.th[k + 1] def cap(self, k): return self.a[1] - 1 + self.s0 if k == 0 else self.a[k + 1] + self.s def S(self, L): return sum(abs(self.theta(k)) for k in range(L, self.top)) def T(self, L): """(lo, hi) of the tails from level t, truncated at top.""" lo = hi = 0 for k in range(L, self.top): v = self.cap(k) * self.theta(k) if v < 0: lo += v else: hi += v return lo, hi def E(self, above=False): return (self.s0 * self.theta(0) + self.s * self.S(1) + (self.tail() if above else 0)) def tail(self): """A bound on s S_top, the part E's sum to top drops, as |theta_(k+2)| < |theta_k|/2.""" return 2 * self.s * (abs(self.theta(self.top)) + abs(self.theta(self.top + 1))) def Tlen(self, L, above=False): """|T_L| summed to top, or from above: the a-part's telescoped |theta_(top-1)| + |theta_top| and the tail added, so that an exact tie w = |T_L| passes.""" lo, hi = self.T(L) if not above: return hi - lo return (hi - lo + abs(self.theta(self.top - 1)) + abs(self.theta(self.top)) + self.tail()) def ov(self, L, above=False): return self.Tlen(L + 1, above) - abs(self.theta(L)) def width(self, L, c, m): return m * (abs(self.theta(L + c)) + abs(self.theta(L + c + 1))) def c_overlap(met, m, depth, cmax=12, above=False): """The least c with w_0 <= E and w_t <= ov_t at every t < depth; None at E <= 0 or when no c <= cmax works. With above, the bars are read from above.""" E = met.E(above) if E <= 0: return None ovs = [met.ov(L, above) for L in range(depth)] for c in range(cmax + 1): if met.width(0, c, m) <= E and all( met.width(L, c, m) <= ovs[L] for L in range(depth)): return c return None # ------------------------------------------------------------ the game class Source: """Where the quotients come from: a periodic alpha (the state is the index of the next quotient in the period) or a class (every letter of the alphabet at every step, one state).""" def __init__(self, period=None, alphabet=None): self.period, self.alphabet = period, alphabet self.A = max(period or alphabet) def start(self): return 0 def nxt(self, st): if self.period: P = self.period return [(P[st], (st + 1) % len(P))] return [(a, 0) for a in self.alphabet] class Game: """The residual game of n -> m n + omega at lookahead `look`, the output capped at a_(t+1) + s (position 0: a_1 - 1 + s0), in frame coordinates (argument (5)). rule=True keeps the below-a-cap rule on the output (the legal output; s = s0 = 0 only).""" def __init__(self, src, m, s, s0, look, omega=0, rule=False, scale=1): assert 0 <= omega <= m and s0 <= s + 1 assert not rule or s == s0 == 0 self.src, self.m, self.s, self.s0 = src, m, s, s0 self.look, self.omega, self.rule = look, omega, rule mu = max(m, 1 + s) self.bx = scale * (mu * (src.A + 1) + 1 + s + m) self.by = scale * (1 + s + m + mu) self.K = 2 * self.by + 1 self.build() def pack(self, x, y): return (x + self.bx) * self.K + (y + self.by) # a state: (branches, quots, srcst, digs, lastzero_in, pos0, # lastzero_out); quots = (a_(t+1) .. a_(t+c+1)), digs = (d_(t+1) .. # d_(t+c)). def cap_out(self, st): a1 = st[1][0] if st[5]: return a1 - 1 + self.s0 if self.rule and not st[6]: return a1 - 1 return a1 + self.s def replies(self, st): for a_new, src2 in self.src.nxt(st[2]): top = a_new if st[4] else a_new - 1 for d_new in range(top + 1): yield a_new, src2, d_new def succ(self, st, e, a_new, src2, d_new): br, quots, digs = st[0], st[1], st[3] seq = digs + (d_new,) d1, a1, m = seq[0], quots[0], self.m bx, by, K = self.bx, self.by, self.K out = [] for v in br: x, y = divmod(v, K) x -= bx y -= by X, Y = y + m * d1, x - e - a1 * y if -bx <= X <= bx and -by <= Y <= by: out.append((X + bx) * K + (Y + by)) if not out: return None return (tuple(sorted(out)), quots[1:] + (a_new,), src2, seq[1:], d_new == 0, False, e == 0) def seed(self, d0): x = self.m * d0 + self.omega return tuple(sorted(self.pack(x, y) for y in range(-self.by, self.by + 1))) def initial(self): """Every legal pre-read d_0 .. d_c with its quotients.""" out, c = [], self.look def rec(quots, srcst, digs, lastzero): if len(quots) == c + 1: out.append((self.seed(digs[0]), quots, srcst, digs[1:], lastzero, True, True)) return k = len(quots) for a, src2 in self.src.nxt(srcst): top = a - 1 if k == 0 else (a if lastzero else a - 1) for d in range(top + 1): rec(quots + (a,), src2, digs + (d,), d == 0) rec((), self.src.start(), (), True) return out def build(self): ids, states = {}, [] self.init = [] for st in self.initial(): if st not in ids: ids[st] = len(states) states.append(st) self.init.append(ids[st]) todo = list(range(len(states))) trans = [None] * len(states) while todo: i = todo.pop() st = states[i] moves = {} for e in range(self.cap_out(st) + 1): zs, nz = [], [] for a_new, src2, d_new in self.replies(st): st2 = self.succ(st, e, a_new, src2, d_new) if st2 is None: break j = ids.get(st2) if j is None: j = ids[st2] = len(states) states.append(st2) trans.append(None) todo.append(j) (zs if d_new == 0 else nz).append(j) else: moves[e] = (len(zs), tuple(zs + nz)) trans[i] = moves self.trans, self.states, self.ids = trans, states, ids self.zero = self.pack(0, 0) def solve(self, flush): """The winning set: safety, alternated with the flush attractor when flush is True. Sets W and dist; returns whether every initial state wins.""" W = set(range(len(self.states))) flushed = [self.zero in st[0] and not any(st[3]) for st in self.states] while True: changed = True while changed: changed = False for i in list(W): if not any(all(j in W for j in succ) for _nz, succ in self.trans[i].values()): W.discard(i) changed = True if not flush: self.W, self.dist = W, None break dist = {i: 0 for i in W if flushed[i]} grew = True while grew: grew = False for i in W: if i in dist: continue best = None for nz, succ in self.trans[i].values(): zs = succ[:nz] if zs and all(j in W for j in succ) and all( j in dist for j in zs): v = 1 + max(dist[j] for j in zs) best = v if best is None else min(best, v) if best is not None: dist[i] = best grew = True if len(dist) == len(W): self.W, self.dist = W, dist break W = set(dist) self.wins = all(i in self.W for i in self.init) return self.wins def choose(self, i): best = None for e, (nz, succ) in self.trans[i].items(): if all(j in self.W for j in succ): key = 0 if self.dist is not None: key = max(self.dist[j] for j in succ[:nz]) if best is None or key < best[0]: best = (key, e) return best[1] def start_state(self, d, quots): c = self.look for i in self.init: st = self.states[i] if st[1] == tuple(quots[:c + 1]) and st[3] == tuple(d[1:c + 1]) \ and st[0] == self.seed(d[0]): return i raise KeyError("no initial state for this pre-read") def read(self, digits, quots, extra=6): """Run the reader on a greedy string at the alpha whose quotients are quots (a_1, a_2, ...): (output, flushed, path), path holding (e, d_(t+1), a_(t+1)) per step.""" c = self.look d = list(digits) + [0] * (c + extra + 2) i = self.start_state(d, quots) out, path = [], [] for t in range(len(digits) + extra): e = self.choose(i) cur = self.states[i] a_new, d_new = quots[t + c + 1], d[t + c + 1] src2 = [s2 for a, s2 in self.src.nxt(cur[2]) if a == a_new][0] st2 = self.succ(cur, e, a_new, src2, d_new) path.append((e, (cur[3] + (d_new,))[0], cur[1][0])) out.append(e) i = self.ids[st2] st = self.states[i] return out, self.zero in st[0] and not any(st[3]), path def least(src, m, s, s0, flush, lo=0, hi=LOOKCAP, omega=0, rule=False, scale=1): """The least lookahead in lo..hi at which the reader wins, with the winning game; (None, None) when none does.""" for c in range(lo, hi + 1): g = Game(src, m, s, s0, c, omega, rule, scale) if g.solve(flush): return c, g return None, None # ------------------------------------------------------------ helpers def maps(): return (2, 3, 4, 5) if FULL else (2, 3) def legal_random(rnd, quots, length): """A random legal greedy string of the given length.""" d, last = [], 0 for k in range(length): cap = quots[0] - 1 if k == 0 else quots[k] top = cap if (k == 0 or last == 0) else cap - 1 d.append(rnd.randint(0, top)) last = d[-1] return d def certify(g, w, m, s, s0, N, omega=0): """Run the reader of game g on every n < N at numeration w; the count of wrong values, broken caps or missing flushes.""" bad = 0 quots = w.a[1:] for n in range(N): out, flushed, _path = g.read(w.digits(n), quots) val = sum(e * w.q(k) for k, e in enumerate(out)) caps = all(e <= (quots[0] - 1 + s0 if k == 0 else quots[k] + s) for k, e in enumerate(out)) if val != m * n + omega or not caps or not flushed: bad += 1 return bad def lineage(g, path): """The flushing branch's trajectory, rebuilt backward from (0, 0) through the recorded (e, d_(t+1), a_(t+1)): its largest |g|, |h| and its seed's g.""" x = y = 0 mx = my = 0 for e, d1, a1 in reversed(path): y0 = x - g.m * d1 x0 = y + e + a1 * y0 x, y = x0, y0 mx, my = max(mx, abs(x)), max(my, abs(y)) return mx, my, x # ------------------------------------------------------------ C1a ranges def section_ranges(): print("== C1a the ranges, the overlaps and the tail lemma") alist = [(n, p) for n, p in PERIODIC] + [("e - 2", None)] worst = 0 for name, per in alist: w = numeration(name, per) if per else Numeration(name, e_minus_2(200)) for s, s0 in SLACKS: met = Metric(w, s, s0, 120) lo, hi = met.T(0) tol = 4 * abs(met.theta(met.top - 1)) dev = abs((hi - lo) - (met.Q + met.E())) ovdev = max(abs(met.ov(L) - abs(met.theta(L + 1)) - s * met.S(L + 1)) for L in range(30)) lemma = min(abs(met.theta(L - 1)) + abs(met.theta(L)) - met.S(L) for L in range(40)) worst = max(worst, float(dev / tol), float(ovdev / tol)) if lemma < 0: worst = float("inf") check("|T_0| = 1 + E and ov_t = |theta_(t+1)| + s S_(t+1) to the " "truncation, the tail lemma at every level read", worst <= 1, f"worst deviation {worst:.2f} of the truncation bound") # ------------------------------------------------------------ P1 the tear def strings_of(w, N, s, s0, k=None): """Every string with e_j <= cap_j and sum e_j q_j = N.""" if k is None: k = w.depth_of(N) if N else 0 if k < 0: return [[]] if N == 0 else [] cap = w.a[1] - 1 + s0 if k == 0 else w.a[k + 1] + s out = [] for e in range(min(cap, N // w.q(k)) + 1): for rest in strings_of(w, N - e * w.q(k), s, s0, k - 1): out.append(rest + [e]) return out def section_tear(): print("== P1 the tear at E = 0") alist = [(n, p) for n, p in PERIODIC] + [("e - 2", None)] total = off = disagree = 0 part_ok = True for name, per in alist: w = numeration(name, per) if per else Numeration(name, e_minus_2(200)) th = [w.value(w.theta(k)) for k in range(40)] alpha = th[0] lo_s = [0 if k % 2 == 0 else w.a[k + 1] for k in range(40)] hi_s = [(w.a[1] - 1 if k == 0 else w.a[k + 1]) if k % 2 == 0 else 0 for k in range(40)] part = next(k for k in range(40) if lo_s[k] != hi_s[k]) part_ok &= part == w.t0 - 1 for N in range(N_TEAR): rep = N * alpha - ((N * alpha + alpha).numerator // (N * alpha + alpha).denominator) for e in strings_of(w, N, 0, 0): e = e + [0] * (40 - len(e)) total += 1 star = sum(ek * th[k] for k, ek in enumerate(e)) if star != rep: off += 1 for ext, gap in ((lo_s, star + alpha), (hi_s, 1 - alpha - star)): for k, ek in enumerate(e): if abs(th[k]) > gap and ek != ext[k]: disagree += 1 check("every string's star is the representative of N alpha mod 1", off == 0, f"{total} strings over N < {N_TEAR} at seven alphas, " f"{off} off") check("a string within eta of an end agrees with that end's extreme " "string wherever |theta_k| > eta", disagree == 0, f"{disagree} disagreements") check("the extreme strings part at position t_0 - 1", part_ok) # ------------------------------------------------------ P2 and P5a class Overlap: """The completion reader of argument (3) at lookahead c, in integer numerators over the convergent's denominator Q.""" def __init__(self, w, m, s, s0, c, depth): self.m, self.c = m, c top = depth + c + 60 self.th = [w.theta(k) for k in range(-1, top + 2)] self.th = [A * w.Q + B * w.P for A, B in self.th] self.Q = w.Q self.depth, self.top = depth, top self.cap = [w.a[1] - 1 + s0] + [w.a[k + 1] + s for k in range(1, top + 1)] self.T = [] for L in range(depth + 2): lo = hi = 0 for k in range(L, top): v = self.cap[k] * self.t(k) lo, hi = (lo + v, hi) if v < 0 else (lo, hi + v) self.T.append((lo, hi)) def t(self, k): return self.th[k + 1] def interval(self, j): """The closed interval between -theta_j and -theta_(j-1).""" a, b = -self.t(j), -self.t(j - 1) return min(a, b), max(a, b) def run(self, d): """Read the legal string d (long enough); returns (ok, M, out, close), close whether |output star - (m x + M)| <= |T_depth|.""" m, c, Q = self.m, self.c, self.Q seen = sum(d[k] * self.t(k) for k in range(c + 1)) ilo, ihi = self.interval(c + 1) lo, hi = m * (seen + ilo), m * (seen + ihi) T0lo, T0hi = self.T[0] M = -((lo - T0lo) // Q) # lo + M Q lands in [T0lo, T0lo + Q) lo, hi = lo + M * Q, hi + M * Q if not (T0lo <= lo and hi <= T0hi): return False, M, [], None committed = 0 out = [] for L in range(self.depth): base = M * Q + m * seen - committed # M + m seen - committed ilo, ihi = self.interval(L + c + 1) jlo, jhi = base + m * ilo, base + m * ihi tl, th_ = self.T[L + 1] best = None for e in range(self.cap[L] + 1): off = e * self.t(L) if off + tl <= jlo and jhi <= off + th_: margin = min(jlo - off - tl, off + th_ - jhi) if best is None or margin > best[0]: best = (margin, e) if best is None: return False, M, out, None e = best[1] out.append(e) committed += e * self.t(L) seen += d[L + c + 1] * self.t(L + c + 1) xstar = sum(d[k] * self.t(k) for k in range(len(d))) err = abs(committed - (m * xstar + M * Q)) tl, th_ = self.T[self.depth] return True, M, out, err <= th_ - tl def section_completion(): print("== P2 the completion reader, and P5a its branch in the box") rnd = random.Random(SEED) alist = [(n, p) for n, p in PERIODIC] + [("e - 2", None)] if FULL: alist += [("[4]", (4,)), ("[5]", (5,))] fails = errs = outbox = runs = 0 cov = {} worst = (0, 0) for name, per in alist: w = numeration(name, per) if per else Numeration(name, e_minus_2(200)) quots = w.a[1:] A = max(quots[:DEPTH + 1]) # a_(t+1) at the track's times 0..DEPTH for m in maps(): for s, s0 in SLACKS[1:]: met = Metric(w, s, s0, DEPTH + 60) c = c_overlap(met, m, DEPTH) cov[(name, m, s, s0)] = c rd = Overlap(w, m, s, s0, c, DEPTH) mu = max(m, 1 + s) bx, by = mu * (A + 1) + 1 + s + m, 1 + s + m + mu for _ in range(N_PLAY): d = legal_random(rnd, quots, DEPTH + c + 4) ok, M, out, close = rd.run(d) runs += 1 if not ok: fails += 1 continue if not close: errs += 1 mx, my = _track(m, out, d, M, quots) worst = (max(worst[0], mx / bx), max(worst[1], my / by)) if mx > bx or my > by: outbox += 1 check("the overlap reader finds a member at every level", fails == 0, f"{runs} runs to depth {DEPTH}, {fails} failures") check("its output star lies within |T_depth| of m x + M", errs == 0, f"{errs} off") check("its true branch stays inside the box", outbox == 0, f"largest |g|/Bg {worst[0]:.2f}, |h|/Bh {worst[1]:.2f}") return cov def _track(m, out, d, M, quots): x, y = m * d[0], -M mx, my = abs(x), abs(y) for t, e in enumerate(out): x, y = y + m * d[t + 1], x - e - quots[t] * y mx, my = max(mx, abs(x)), max(my, abs(y)) return mx, my # ------------------------------------------------------------ P3 floors def section_floors(): print("== P3 the floors at every slack") alist = PERIODIC if FULL else PERIODIC[:4] tiles = fits = 0 least_excess = None for name, per in alist: w = numeration(name, per) keys = w.keys(N_FLOOR) for m in (2, 3): for s in range(4): met = Metric(w, s, s, 120) t = next(t for t in range(1, 60) if m * (met.T(t)[1] - met.T(t)[0]) < met.Q) width = met.T(t)[1] - met.T(t)[0] for c in range(4): if t + c >= len(keys): break groups = {} for n, key in enumerate(keys[t + c]): groups.setdefault(key, []).append(n) for ns in groups.values(): if len(ns) < 12: continue pts = sorted((n // m) * w.P % w.Q for n in ns) gaps = [b - a for a, b in zip(pts, pts[1:])] gaps.append(pts[0] + w.Q - pts[-1]) hull = w.Q - max(gaps) tiles += 1 ex = (hull - width) / w.Q least_excess = ex if least_excess is None \ else min(least_excess, ex) if hull <= width: fits += 1 check("floor(n/m): no input tile's images fit a depth-t* cylinder", fits == 0, f"{tiles} (tile, m, s, c) tests, m = 2, 3, s = s_0 " f"= 0..3, c = 0..3, least " f"hull less |T_t*| = {least_excess:.4f}") # ------------------------------------------------------ C1b-d, P1, P4, P5b def section_controls(): print("== C1b the legal output through the game") ok = True for name, per in PERIODIC: src = Source(period=per) ident = least(src, 1, 0, 0, True, rule=True)[0] succ = least(src, 1, 0, 0, True, omega=1, rule=True)[0] x2 = least(src, 2, 0, 0, True, rule=True)[0] x3 = least(src, 3, 0, 0, True, rule=True)[0] free = least(src, 1, 0, 0, True, omega=1)[0] row = (ident, succ, x2, x3, free) ok &= row == (0, 1, None, None, 0) print(f" {name:20s} id {ident} n+1 {succ} x2 {x2} x3 {x3}" f" n+1 rule dropped {free}") check("identity 0, n + 1 at 1, x 2 and x 3 at no c <= LOOKCAP; " "n + 1 at 0 once the rule is dropped", ok) def section_grid(cov): print("== the grid: c_saf / c_int per (alpha, m, (s, s_0)), c_ov after") alist = PERIODIC if FULL else [PERIODIC[0], PERIODIC[1], PERIODIC[3]] bad = earlier_off = floor_off = saf_over = tear_off = 0 grid = {} for name, per in alist: src = Source(period=per) w = numeration(name, per) A = max(per) print(f" {name}") for m in maps(): row = [] for j, (s, s0) in enumerate(SLACKS): c_ov = cov.get((name, m, s, s0)) hi = max(LOOKCAP, (c_ov or 0) + 1) c_saf, _g = least(src, m, s, s0, False, hi=hi) c_int, g = least(src, m, s, s0, True, lo=c_saf or 0, hi=hi) \ if c_saf is not None else (None, None) if g is not None: bad += certify(g, w, m, s, s0, N_CHECK) grid[(name, m, s, s0)] = (c_saf, c_int) if c_int != EARLIER[name][m - 2][j]: earlier_off += 1 digitwise = s >= (m - 1) * A if (c_int == 0) != digitwise or c_int == 1: floor_off += 1 if (s, s0) == (0, 0) and c_saf is not None: # no reader at all tear_off += 1 if c_ov is not None and (c_saf is None or c_saf > c_ov): saf_over += 1 row.append(f"{_fmt(c_saf)}/{_fmt(c_int)} {_fmt(c_ov)}") print(f" x{m} " + " ".join(f"{r:7s}" for r in row)) tally = {} for c_saf, c_int in grid.values(): if c_saf is not None and c_int is not None: tally[c_int - c_saf] = tally.get(c_int - c_saf, 0) + 1 print(" c_int - c_saf over the finite cells: " + ", ".join( f"{k}: {v}" for k, v in sorted(tally.items()))) ovs = [cov[(name, m, s, s0)] for name, _ in alist for m in maps() for s, s0 in SLACKS if cov.get((name, m, s, s0)) is not None] print(f" c_ov over the grid's cells with E > 0: {min(ovs)} to " f"{max(ovs)}") check("every winning strategy is correct on every n < N_CHECK", bad == 0, f"{bad} bad") check("c_int agrees with the earlier independent engine", earlier_off == 0, f"{earlier_off} cells off") check("the (0, 0) column: x m reads at no c <= LOOKCAP", tear_off == 0) check("c_int is 0 exactly where s >= (m - 1) a_max, else >= 2", floor_off == 0, f"{floor_off} cells off") check("c_saf <= c_ov at every cell with E > 0", saf_over == 0, f"{saf_over} cells over") return grid def _fmt(c): return "-" if c is None else str(c) def section_digitwise(): print("== P4a,b the flush floor's two halves") bad = 0 for name, per in PERIODIC: w = numeration(name, per) A = max(per) for m in maps(): s = (m - 1) * A a1 = w.a[1] for n in range(N_CHECK): d = w.digits(n) + [0, 0] e = [m * dk for dk in d] e[0], carry = (m * d[0]) % a1, (m * d[0]) // a1 e[1] += carry val = sum(ek * w.q(k) for k, ek in enumerate(e)) caps = e[0] <= a1 - 1 and all( e[k] <= w.a[k + 1] + s for k in range(1, len(e))) if val != m * n or not caps: bad += 1 check("the digitwise reader at s = (m - 1) a_max, s_0 = 0: correct", bad == 0, f"{bad} bad over n < {N_CHECK}") wrong = 0 shown = [] for name, per in PERIODIC: w = numeration(name, per) P = len(per) for m in maps(): for phase in range(P): k = next(k for k in range(2, 200) if k % P == phase and w.q(k - 1) > m * w.a[k + 1]) N = m * w.a[k + 1] V = N * w.q(k) coins = [w.q(j) for j in range(k - 1, 200) if w.q(j) <= V] ways = [1] + [0] * V for q in coins: for v in range(q, V + 1): ways[v] += ways[v - q] if ways[V] != 1: wrong += 1 if len(shown) < 3: shown.append(f"{name} x{m} k={k}: {V} = {N} q_{k}") check("m a_(k+1) q_k has exactly one string from level k - 1 (any " "digit sizes), e_k = m a_(k+1)", wrong == 0, f"{wrong} off; e.g. " + "; ".join(shown)) # ------------------------------------------------------------ P5c, P5d def section_band(): print("== P5d the band cells: c_ov = 1 < 2 <= c_int") ok = True cells = BAND if FULL else BAND[:1] for name, per, m, s in cells: w = numeration(name, per) met = Metric(w, s, s, DEPTH + 60) c_ov = c_overlap(met, m, DEPTH) src = Source(period=per) c_saf, _g = least(src, m, s, s, False, hi=3) c_int, g = least(src, m, s, s, True, hi=3) bad = certify(g, w, m, s, s, N_CHECK) if g else None print(f" {name:12s} x{m} s = s_0 = {s}: c_ov {c_ov} c_saf " f"{c_saf} c_int {c_int} states {len(g.states) if g else '-'}" f" bad {bad}") ok &= (c_ov == 1 and c_saf is not None and c_saf <= 1 and c_int == 2 and bad == 0) check("a strict flush price at every band cell", ok) if not FULL: return print("== P5c c_saf at twice the box") same = True for name, per, m, s, s0 in [("golden [1]", (1,), 3, 0, 1), ("silver [2]", (2,), 2, 1, 1), ("sqrt(3) - 1 [1, 2]", (1, 2), 3, 2, 2), ("bronze [3]", (3,), 2, 2, 2)]: src = Source(period=per) one = least(src, m, s, s0, False, hi=6)[0] two = least(src, m, s, s0, False, hi=6, scale=2)[0] print(f" {name:20s} x{m} ({s},{s0}): c_saf {one} at the box, " f"{two} at twice it") same &= one == two check("c_saf does not move when the box doubles", same) # ------------------------------------------------------------ P7 the owed def conj_ratios(per): """zeta'_t by t mod p: the fixed point of z -> a_t + 1/z run round the period, a_t = per[(t - 1) % p] (a_0 read as a_p).""" p, z = len(per), 1.0 out = [0.0] * p for t in range(1, 400 * p + 1): z = per[(t - 1) % p] + 1 / z if t > 399 * p: out[t % p] = z return out def real_ratios(per): """|theta_t/theta_(t-1)| = [0; a_(t+1), a_(t+2), ...] by t mod p, the control's transplant.""" p = len(per) out = [] for r in range(p): x = 0.0 for k in range(400 * p, -1, -1): x = 1 / (per[(r + k) % p] + x) out.append(x) return out def tentative(g, st, Z, conj=True): """Every branch of state st as (G, H, u~): (G, H) its tentative pair, the pending digits absorbed exactly, q_(t+j) = U_j q_t + V_j q_(t-1) by q_(k+1) = a_(k+1) q_k + q_(k-1); u~ by the product formula, Z the ratio by t mod p, checked against G Z_t + H when Z is zeta' (the identity needs Z_(t+1) = a_(t+1) + 1/Z_t, which the control's real ratio does not obey).""" c, p = g.look, len(Z) t = (st[2] - c - 1) % p prods, acc = [], Z[t] for j in range(1, c + 1): acc *= Z[(t + j) % p] prods.append(acc) pend = g.m * sum(d * pr for d, pr in zip(st[3], prods)) (U0, V0), (U1, V1) = (0, 1), (1, 0) # q_(t-1), q_t PG = PH = 0 for j in range(1, c + 1): a = st[1][j - 1] # a_(t+j) (U0, V0), (U1, V1) = (U1, V1), (a * U1 + U0, a * V1 + V0) PG += g.m * st[3][j - 1] * U1 PH += g.m * st[3][j - 1] * V1 out = [] for v in st[0]: x, y = divmod(v, g.K) x -= g.bx y -= g.by G, H = x + PG, y + PH u = x * Z[t] + y + pend assert not conj or abs(u - (G * Z[t] + H)) <= 1e-6 * (1 + abs(u)) out.append((G, H, u)) return out def safe_within(g, good): """The safety game's greatest fixed point inside the states marked good.""" W = {i for i in range(len(g.states)) if good[i]} changed = True while changed: changed = False for i in list(W): if not any(all(j in W for j in succ) for _nz, succ in g.trans[i].values()): W.discard(i) changed = True return W def section_owed(grid): print("== P7 the integer game is the safety game on u~ >= 0") off = ctrl_off = zero_bad = kept = compared = 0 margin = float("inf") for name, per in PERIODIC: if not any(k[0] == name for k in grid): continue Zc, Zr = conj_ratios(per), real_ratios(per) print(f" {name:20s} zeta' by t mod p: " + ", ".join(f"{z:.6f}" for z in Zc)) src = Source(period=per) for m in maps(): for s, s0 in SLACKS: c_int = grid[(name, m, s, s0)][1] cell_off = cell_ctrl = False for c in range((LOOKCAP if c_int is None else c_int) + 1): g = Game(src, m, s, s0, c) assert g.solve(True) == (c == c_int) good, goodr = [], [] for st in g.states: us = tentative(g, st, Zc) if g.zero in st[0] and not any(st[3]) and not any( G == 0 and H == 0 and abs(u) <= 1e-9 for G, H, u in us): zero_bad += 1 margin = min([margin] + [abs(u) for G, H, u in us if (G, H) != (0, 0)]) good.append(any(u >= -1e-9 for _G, _H, u in us)) goodr.append(any(u >= -1e-9 for _G, _H, u in tentative(g, st, Zr, False))) cell_off |= safe_within(g, good) != g.W cell_ctrl |= safe_within(g, goodr) != g.W compared += 1 kept += len(g.W) > 0 del g off += cell_off ctrl_off += cell_ctrl cells = len(grid) print(f" {compared} winning sets compared over {cells} cells, every " f"c to c_int (to LOOKCAP where none), {kept} non-empty") print(f" cells off: {off} of {cells}; control (the real side's " f"ratio for zeta'): {ctrl_off} of {cells} off") print(f" flushed states without a u~ = 0 branch: {zero_bad}; least " f"|u~| over branches of tentative pair not (0, 0): {margin:.3e}") check("W_int is the safety game's set on the states with a branch of " "u~ >= 0, at every cell and c", off == 0) check("every flushed state has a branch with u~ = 0; the float margin " "above 1e-7", zero_bad == 0 and margin > 1e-7) check("control: the real-side ratio moves the set at some cell", ctrl_off > 0) # ------------------------------------------------------------ P8 the cone class Cone: """Argument (3)'s reader as an integer reader of n -> m n + omega at lookahead c, windows and caps at slack (s, s0): the owed integer N and its star kept exactly (numerators over Q), its cone coordinates N = K q_(t+1) + L q_t read off them at every step. With seam, at the (0, 0) windows, a target J_0 holding its lift's seam -1 is read by (11)'s two moves, e_0 = 0 and e_1 = a_2 + 1, so the output lies under the (1, 0) caps by construction.""" def __init__(self, w, m, s, s0, c, depth, seam=False): self.w, self.m, self.c, self.depth = w, m, c, depth self.seam_rule = seam top = depth + c + 60 self.th = [w.q(k) * w.P - w.p(k) * w.Q for k in range(-1, top + 2)] self.cap = [w.a[1] - 1 + s0] + [w.a[k + 1] + s for k in range(1, top + 1)] lo = hi = 0 self.T = [None] * (depth + 2) for k in range(top - 1, -1, -1): v = self.cap[k] * self.t(k) lo, hi = (lo + v, hi) if v < 0 else (lo, hi + v) if k < depth + 2: self.T[k] = (lo, hi) def t(self, k): return self.th[k + 1] def interval(self, j): a, b = -self.t(j), -self.t(j - 1) return min(a, b), max(a, b) def coords(self, t, N, sig): w = self.w X = (N * w.P - sig) // w.Q # K p_(t+1) + L p_t, exactly D = w.q(t + 1) * w.p(t) - w.q(t) * w.p(t + 1) return ((N * w.p(t) - w.q(t) * X) // D, (w.q(t + 1) * X - w.p(t + 1) * N) // D) def read(self, d, omega, pick): """(ok, why, steps with K < 0 or L < 0): the least lift K_0, then the least or greatest member holding J_t, until N = 0 with the input absorbed and eight zero digits after; self.seam says whether the seam's moves were taken.""" w, m, c, Q = self.w, self.m, self.c, self.w.Q n = sum(x * w.q(k) for k, x in enumerate(d)) d = list(d) + [0] * (self.depth + c + 2) N = m * sum(d[k] * w.q(k) for k in range(c + 1)) + omega ilo, ihi = self.interval(c + 1) lo, hi = self.T[0] K0 = -((hi - N * w.P - m * ihi) // Q) sig = N * w.P - K0 * Q # the star N alpha - K_0 self.neg_at, self.K0 = None, K0 self.seam = self.seam_rule and sig + m * ilo < lo if sig + m * (ihi if self.seam else ilo) < lo: return False, "no lift", 0 out, neg, done = [], 0, None for t in range(self.depth): K, L = self.coords(t, N, sig) if (K < 0 or L < 0) and self.neg_at is None: self.neg_at = t neg += K < 0 or L < 0 if done is None and N == 0 and sig == 0 \ and not any(d[t + c + 1:]): done = t if done is not None and t >= done + 8: break u = self.t(t) if self.seam and t < 2: e = 0 if t == 0 else w.a[2] + 1 else: ilo, ihi = self.interval(t + c + 1) jlo, jhi = sig + m * ilo, sig + m * ihi tl, th = self.T[t + 1] if u > 0: elo, ehi = -((th - jhi) // u), (jlo - tl) // u else: elo, ehi = -((jlo - tl) // -u), (th - jhi) // -u elo, ehi = max(elo, 0), min(ehi, self.cap[t]) if elo > ehi: return False, f"no member at t = {t}", neg e = elo if pick == "least" else ehi out.append(e) N, sig = N - e * w.q(t), sig - e * u dd = d[t + c + 1] N, sig = N + m * dd * w.q(t + c + 1), sig + m * dd * self.t(t + c + 1) val = sum(e * w.q(k) for k, e in enumerate(out)) if done is None or any(out[done:]) or val != m * n + omega: return False, "not ended" if done is None else "value", neg return True, "", neg def cone_inputs(w, rnd): count, length = (100, 60) if FULL else (20, 40) quots = w.a[1:] return ([w.digits(n) for n in range(N_CHECK)] + [legal_random(rnd, quots, length) for _ in range(count)]) def cone_cell(w, m, s, s0, c, ins, omegas, picks, breaks=None, seam=False, whys=None): """(failures, negative-coordinate steps, the first failure, seam reads); breaks, if given, tallies the reads whose first negative step is the lift's (t = 0) or a member's, whys every failure's reason.""" rd = Cone(w, m, s, s0, c, 110, seam) bad = neg = seams = 0 first = None for omega in omegas: for pick in picks: for d in ins: ok, why, ng = rd.read(d, omega, pick) neg += ng seams += rd.seam if breaks is not None and rd.neg_at is not None: breaks["lift" if rd.neg_at == 0 else "member"] += 1 if not ok: bad += 1 first = first or why if whys is not None: whys[why] = whys.get(why, 0) + 1 return bad, neg, first, seams def c_seam(w, m, strict, depth=110): """The least c with w_0 < |theta_2| (strict) or w_0 <= |theta_1|, and w_t <= |theta_(t+1)| at 1 <= t < depth: the seam reader's bars of (11), or with its own bar loosened to the s = 0 one.""" def th(k): return abs(w.q(k) * w.P - w.p(k) * w.Q) def wid(t, c): return m * (th(t + c) + th(t + c + 1)) for c in range(20): ok0 = wid(0, c) < th(2) if strict else wid(0, c) <= th(1) if ok0 and all(wid(t, c) <= th(t + 1) for t in range(1, depth)): return c return None def section_cone(grid): print("== P8 the overlap reader at the s = 0 windows is an integer reader") rnd = random.Random(SEED + 2) names = sorted({k[0] for k in grid}, key=[n for n, _ in PERIODIC].index) alist = [(n, numeration(n, p)) for n, p in PERIODIC if n in names] alist.append(("e - 2", Numeration("e - 2", e_minus_2(200)))) if FULL: alist.append(("random {1, 2, 3}", Numeration("random {1, 2, 3}", [ rnd.choice((1, 2, 3)) for _ in range(200)]))) known = known_pass = over = above = equal = cells = 0 fails = negs = ctrl_fail = ctrl_neg = 0 lift_cells = member_cells = zero_cells = only_zero = zero_k0 = 0 sk = sk_pass = s_over = s_above = s_fail = s_neg = s_never = 0 pl_cells = pl_bites = 0 pl_whys = {} for name, w in alist: ins = cone_inputs(w, rnd) row, seam_row = [], [] for m in maps(): cells += 1 c0 = c_overlap(Metric(w, 0, 1, 170), m, 110) over += c0 > 2 * (m - 1).bit_length() + 2 c_int = grid.get((name, m, 0, 1), (None, None))[1] if c_int is not None: above += c_int > c0 equal += c_int == c0 if c_int >= 1: known += 1 known_pass += cone_cell(w, m, 0, 1, c_int - 1, ins, (0,), ("least",))[0] == 0 for c in range(c0, c0 + (3 if FULL else 1)): bad, neg, first, _ = cone_cell(w, m, 0, 1, c, ins, (0, m), ("least", "greatest")) fails += bad negs += neg if bad or neg: print(f" FAIL {name} x{m} c {c}: {bad} bad, {neg} " f"negative steps, first {first}") br = {"lift": 0, "member": 0} bad, neg, first, _ = cone_cell(w, m, 1, 1, c0, ins, (0,), ("least",), br) ctrl_fail += bad > 0 ctrl_neg += neg > 0 rz = Cone(w, m, 1, 1, c0, 110) zero_bad = not rz.read(ins[0], 0, "least")[0] zero_cells += zero_bad only_zero += zero_bad and bad == 1 zero_k0 += zero_bad and rz.K0 == -1 lift_cells += br["lift"] > 0 member_cells += br["member"] > 0 row.append(f"x{m} c_ov {c0} c_int {_fmt(c_int)} | (1, 1): " f"{bad} bad, breaks lift {br['lift']} member " f"{br['member']}") csr, cpl = c_seam(w, m, True), c_seam(w, m, False) s_over += csr > 2 * (m - 1).bit_length() + 3 ci = grid.get((name, m, 1, 0), (None, None))[1] if ci is not None: s_above += ci > csr if ci >= 1: sk += 1 sk_pass += cone_cell(w, m, 0, 0, ci - 1, ins, (0,), ("least",), seam=True)[0] == 0 taken = 0 for c in range(csr, csr + (2 if FULL else 1)): bad, neg, first, seams = cone_cell( w, m, 0, 0, c, ins, (0, m), ("least", "greatest"), seam=True) s_fail += bad s_neg += neg taken += seams if bad or neg: print(f" SEAM FAIL {name} x{m} c {c}: {bad} bad, " f"{neg} negative steps, first {first}") s_never += taken == 0 seam_row.append(f"x{m} c_sr {csr} c_int(1, 0) {_fmt(ci)} seam " f"{taken}") if cpl < csr: pl_cells += 1 pl_bites += cone_cell(w, m, 0, 0, cpl, ins, (0,), ("least",), seam=True, whys=pl_whys)[0] > 0 print(f" {name:20s} " + "; ".join(row)) print(f" {'':20s} seam: " + "; ".join(seam_row)) print(f" known answer: the reader at c_int - 1 passes at {known_pass} " f"of {known} cells") print(f" failures at c >= c_ov(0, 1): {fails}; steps with K < 0 or " f"L < 0: {negs}") print(f" c_ov(0, 1) above 2 ceil(log2 m) + 2: {over} of {cells}; " f"c_int above c_ov(0, 1): {above}, equal at {equal}") print(f" control, the (1, 1) windows at c_ov(0, 1): fails at " f"{ctrl_fail}, a negative coordinate at {ctrl_neg} (by the lift at " f"{lift_cells}, by a member at {member_cells}), of {cells} cells; " f"n = 0 fails at {zero_cells}, alone at {only_zero}, its lift " f"K_0 = -1 at {zero_k0}") check("known answer: the reader at c_int - 1 fails at every cell", known_pass == 0 and known > 0) check("the overlap reader at the (0, 1) windows reads every input and " "keeps K, L >= 0", fails == 0 and negs == 0) check("c_ov(0, 1) <= 2 ceil(log2 m) + 2 and c_int <= c_ov(0, 1)", over == 0 and above == 0) check("control: the (1, 1) windows at c_ov(0, 1) fail at some cell", ctrl_fail > 0) print(f" seam, known answer: the seam reader at c_int(1, 0) - 1 " f"passes at {sk_pass} of {sk} cells") print(f" seam failures at c >= c_sr: {s_fail}; steps with K < 0 or " f"L < 0: {s_neg}; cells where the seam is never taken: {s_never} " f"of {cells}") print(f" c_sr above 2 ceil(log2 m) + 3: {s_over} of {cells}; " f"c_int(1, 0) above c_sr: {s_above}") print(f" plant, the seam's bar loosened to w_0 <= |theta_1|: c_pl < " f"c_sr at {pl_cells} cells, fails at {pl_bites}, its failures " f"{dict(sorted(pl_whys.items()))}") check("seam known answer: the seam reader at c_int(1, 0) - 1 fails at " "every cell", sk_pass == 0 and sk > 0) check("the seam reader at (1, 0) reads every input, keeps K, L >= 0 and " "takes the seam at every cell", s_fail == 0 and s_neg == 0 and s_never == 0) check("c_sr <= 2 ceil(log2 m) + 3 and c_int(1, 0) <= c_sr", s_over == 0 and s_above == 0) check("plant: the seam reader at the loosened bar fails at some cell", pl_bites > 0) # ------------------------------------------------------------ P9 the cylinder def c_floor(met, m, depth, bar="T", above=True): """The least c with w_t <= the bar at every t < depth with |T_(t+1)| < 1, read from above unless above is False: bar "T" is (12)'s |T_(t+1)|, "ov" c_ov's ov_t (too strict, a plant), "up" the level above's |T_t| (too lax, a plant).""" ts = [t for t in range(depth) if met.Tlen(t + 1, above) < met.Q] bars = [met.ov(t, above) if bar == "ov" else met.Tlen(t if bar == "up" else t + 1, above) for t in ts] for c in range(41): if all(met.width(t, c, m) <= b for t, b in zip(ts, bars)): return c return None def _tally(xs): return ", ".join(f"{g}: {xs.count(g)}" for g in sorted(set(xs))) def section_cylinder(grid, cov): print("== P9 the cylinder bound c_lo: below c_saf and c_int, c_ov " "within max(2, t_1)") over = [0, 0] def t_one(met, depth, gap): t1 = next(t for t in range(depth) if met.Tlen(t + 1, True) < met.Q) over[0] += gap > max(2, t1) over[1] += t1 > max(1, 2 * (2 * met.s).bit_length()) return t1 phi = (1 + 5 ** 0.5) / 2 w = numeration("golden [1]", (1,)) off = 0 for m in range(2, 10): for s, s0 in SLACKS[1:]: met = Metric(w, s, s0, 120) lo = next(c for c in range(40) if m * phi ** -c <= 1 + s + 1e-12) ov = next(c for c in range(40) if m * phi ** -c <= s + min(phi ** -2, s0 / phi) + 1e-12) off += (c_floor(met, m, 60), c_overlap(met, m, 60)) != (lo, ov) check("control: c_lo and c_ov at golden x 2 .. x 9 equal their closed " "forms", off == 0, f"{off} of 40 off") x_saf = x_int = strict_over = ties = tie_const = moved = reads = 0 zero_off = 0 gaps, below, at_s0, up_gold = [], [], [], [] for name, per in PERIODIC: if (name, 2, 0, 1) not in grid: continue w = numeration(name, per) for m in maps(): for s, s0 in SLACKS[1:]: met = Metric(w, s, s0, 120) lo = c_floor(met, m, 60) tie = c_floor(met, m, 60, above=False) != lo ties += tie tie_const += tie and len(per) == 1 and s == (m - 1) * per[0] c_ov = cov[(name, m, s, s0)] moved += c_overlap(met, m, 60, above=True) != c_ov reads += 1 c_saf, c_int = grid[(name, m, s, s0)] x_saf += c_saf is not None and lo > c_saf x_int += c_int is not None and lo > c_int strict_over += c_saf is not None and \ c_floor(met, m, 60, "ov") > c_saf if name.startswith("golden") and s == 0: up_gold.append(c_ov - c_floor(met, m, 60, "up")) gaps.append(c_ov - lo) t_one(met, 60, c_ov - lo) if c_saf is not None: below.append(c_saf - lo) zero_off += (lo == 0) != (c_saf == 0) if s == 0 and c_int is not None: at_s0.append(c_int - lo) print(f" controls: the bar ov_t puts c_lo above c_saf at {strict_over} " f"cells; the bar |T_t| at golden s = 0 gives gaps {up_gold}") print(f" ties (a bar met exactly, missed when summed to top): {ties} " f"cells, at s = (m - 1)a, a the constant quotient: {tie_const}") print(f" c_lo > c_saf at {x_saf} cells, c_lo > c_int at {x_int}") print(f" c_ov - c_lo over the grid: {_tally(gaps)}") print(f" c_saf - c_lo: {_tally(below)}; c_lo = 0 and c_saf = 0 " f"disagree at {zero_off} cells") print(f" c_int - c_lo at s = 0: {_tally(at_s0)}") check("control: the bar ov_t, too strict, puts c_lo above c_saf at some " "cell", strict_over > 0) check("control: the bar |T_t|, too lax, gives a gap of 3 at golden s = 0", 3 in up_gold) check("c_lo <= c_saf and c_lo <= c_int at every finite grid cell", x_saf + x_int == 0) check("0 <= c_ov - c_lo <= 2 at every grid cell", min(gaps) >= 0 and max(gaps) <= 2) rnd = random.Random(SEED + 2) rq = [rnd.choice((1, 2, 3)) for _ in range(200)] # P8's random alpha far = 0 for name, w in (("e - 2", Numeration("e - 2", e_minus_2(200))), ("random {1, 2, 3}", Numeration("random {1, 2, 3}", rq))): short = all(Metric(w, s, s0, 170).Tlen(3, True) < w.Q for s, s0 in SLACKS[1:]) g = [] for m in maps(): for s, s0 in SLACKS[1:]: met = Metric(w, s, s0, 170) c_ov = c_overlap(met, m, 110) moved += c_overlap(met, m, 110, above=True) != c_ov reads += 1 g.append(c_ov - c_floor(met, m, 110)) t_one(met, 110, g[-1]) print(f" {name}: |T_3| < 1 at every slack: {'yes' if short else 'no'}" f"; c_ov - c_lo {min(g)} to {max(g)}") far += not short or min(g) < 0 or max(g) > 2 check("e - 2 and the random alpha: |T_3| < 1, 0 <= c_ov - c_lo <= 2", far == 0) H, meets = 10 ** 8, 0 for N in range(2, 8): w = Numeration(f"fam{N}", [1] * (N + 1) + [H] * 60) s = next(s for s in range(1, 10 ** 4) if Metric(w, s, 0, N + 50).Tlen(N) >= w.Q) best = None for e in range(1, 13): met = Metric(w, s, 1, N + 50) lo, ov = c_floor(met, 2 ** e, N + 40), \ c_overlap(met, 2 ** e, N + 40, 40) moved += c_overlap(met, 2 ** e, N + 40, 40, True) != ov reads += 1 t1 = t_one(met, N + 40, ov - lo) if best is None or ov - lo > best[0]: best = (ov - lo, 2 ** e, lo, ov) meets += best[0] == max(2, t1) print(f" family N {N}: s {s}, t_1 {t1}; largest c_ov - c_lo " f"{best[0]} at x{best[1]} (c_lo {best[2]}, c_ov {best[3]})") print(f" gap above max(2, t_1): {over[0]}; t_1 above max(1, 2 " f"ceil(log2(2s + 1))): {over[1]}; c_ov with its bars read from " f"above moves at {moved} of {reads} cells") check("c_ov - c_lo <= max(2, t_1), t_1 <= max(1, 2 ceil(log2(2s + 1))), " "at every cell read", over == [0, 0]) check("the family [1 x (N + 1), 10^8, ...] meets max(2, t_1) at N = " "2 .. 7", meets == 6) check("c_ov's bars read from above move no c_ov at any cell read", moved == 0) # ------------------------------------------------------------ P9(b) the pin NPIN = 20000 def _hull(x, y): return (min(x, y), max(x, y)) def _inside(a, b): return b[0] <= a[0] and a[1] <= b[1] def zero_cyl(met, L): """I_L, the stars of the inputs with d_0 .. d_(L-1) all 0.""" return _hull(-met.theta(L), -met.theta(L - 1)) def sub_cyls(met, j): """I_j split by the digit d_j: C_0 = I_(j+1), then C_1 .. C_a.""" th, th1 = met.theta(j), met.theta(j + 1) return [_hull(-th1, -th)] + [_hull((d - 1) * th - th1, d * th - th1) for d in range(1, met.a[j + 1] + 1)] def members(met, L): lo, hi = zero_cyl(met, L + 1) return [(lo + e * met.theta(L), hi + e * met.theta(L)) for e in range(met.cap(L) + 1)] def pin_levels(met, depth): return [t for t in range(depth) if abs(met.theta(t)) + abs(met.theta(t + 1)) < met.Q] def pin_bar(met, m, c, t, two): """Z(c) at level t, s = 0: m I_j inside I_(t+1), j = t + c + 1 (one level), and with two, each m C_d inside one member of T_(t+1).""" j = t + c + 1 if not _inside((m * zero_cyl(met, j)[0], m * zero_cyl(met, j)[1]), zero_cyl(met, t + 1)): return False mem = members(met, t + 1) if two else [] return all(any(_inside((m * p[0], m * p[1]), q) for q in mem) for p in (sub_cyls(met, j) if two else [])) def c_lo2(met, m, two=True, depth=60, least_pass=False): """1 + the largest c below 30 at which Z(c) fails at some level read (Z(c) holds at every c from 30 on); with least_pass, the least c at which it holds.""" ts = pin_levels(met, depth) ok = [all(pin_bar(met, m, c, t, two) for t in ts) for c in range(30)] assert ok[-1] return ok.index(True) if least_pass else \ 1 + max(c for c in range(30) if not ok[c]) def pinning(w, met): """The first level t at which some N != 0 below q_(t+1) + q_t has a K - N alpha strictly inside I_(t+1), or None; and the levels read.""" read = 0 for t in pin_levels(met, 60): top = w.q(t + 1) + w.q(t) if top > NPIN: break lo, hi = zero_cyl(met, t + 1) read += 1 for N in range(1, top): base = (N * w.P) // w.Q if any(lo < K * w.Q - N * w.P < hi for K in (base - 1, base, base + 1, base + 2)): return t, read return None, read def section_pinned(grid): print("== P9(b) the pinned zero cylinder at (s, s_0) = (0, 1): c_lo2 " "between c_lo and c_saf") off = 0 for name, per in PERIODIC: met = Metric(numeration(name, per), 0, 1, 120) for j in range(1, 90): ps = sorted(sub_cyls(met, j)) off += (ps[0][0], ps[-1][1]) != zero_cyl(met, j) off += any(a[1] != b[0] for a, b in zip(ps, ps[1:])) ms = members(met, j) off += (min(q[0] for q in ms), max(q[1] for q in ms)) \ != zero_cyl(met, j) check("control: the sub-cylinders tile I_j and the members' hull is " "I_L at j, L < 90", off == 0, f"{off} faults over the six alpha") phi = (1 + 5 ** 0.5) / 2 gmet = Metric(numeration("golden [1]", (1,)), 0, 1, 120) got = [c_lo2(gmet, m) for m in range(2, 10)] lo = [next(c for c in range(40) if m * phi ** -c <= 1 + 1e-12) for m in range(2, 10)] check("control: golden x 2 .. x 9, c_lo2 is c_lo rounded up to even", got == [c + c % 2 for c in lo], f"{got}") smet = Metric(numeration("silver [2]", (2,)), 0, 1, 120) one, two = c_lo2(smet, 4, False), c_lo2(smet, 4) check("control: silver x 4, the seam bar lifts the one-level bar 2 to 3", (one, two) == (2, 3), f"one level {one}, two levels {two}") alone, mono = [], 0 for name, per in PERIODIC: w = numeration(name, per) met = Metric(w, 0, 1, 120) bad, read = pinning(w, met) alone.append(read if bad is None else f"another N at t = {bad}") mono += sum(c_lo2(met, m) != c_lo2(met, m, least_pass=True) for m in range(2, 10)) print(f" pinning, the levels with q_(t+1) + q_t <= {NPIN} read: " f"{alone}") check("pinning: N = 0 alone at every level read, at the six alpha", all(isinstance(r, int) for r in alone)) check("Z(c) fails below c_lo2 and holds from it, x 2 .. x 9 at the six " "alpha", mono == 0, f"{mono} of 48 differ") x_lo = x_saf = x_int = x_gap = 0 gaps, moves, lifted, flat = [], [], [], [] for name, per in PERIODIC: if (name, 2, 0, 1) not in grid: continue met = Metric(numeration(name, per), 0, 1, 120) row = [] for m in maps(): lo, par, two = c_floor(met, m, 60), c_lo2(met, m, False), \ c_lo2(met, m) c_saf, c_int = grid[(name, m, 0, 1)] x_lo += lo > two x_saf += two > c_saf x_int += c_saf > c_int gaps.append(c_int - two) if two > lo: lifted.append(c_int - two) x_gap += c_int - two > 1 else: flat.append(c_int - two) if two != par: moves.append(f"{name.split()[0]} x{m}") row.append(f"x{m} {lo}/{par}/{two}/{c_saf}/{c_int}") print(f" {name:20s} " + " ".join(row)) print(f" (c_lo / one level / c_lo2 / c_saf / c_int) c_int - c_lo2: " f"{_tally(gaps)}; where c_lo2 > c_lo: {_tally(lifted)}; where " f"c_lo2 = c_lo: {_tally(flat)}; the seam bar moves c_lo2 at " f"{moves or 'none'}") check("c_lo <= c_lo2 <= c_saf <= c_int at every grid cell at (0, 1)", x_lo + x_saf + x_int == 0, f"{x_lo}, {x_saf}, {x_int} off") check("c_int - c_lo2 <= 1 wherever c_lo2 > c_lo", x_gap == 0) rnd = random.Random(SEED + 2) rq = [rnd.choice((1, 2, 3)) for _ in range(200)] # P8's random alpha far = 0 for name, w in (("e - 2", Numeration("e - 2", e_minus_2(200))), ("random {1, 2, 3}", Numeration("random {1, 2, 3}", rq))): met = Metric(w, 0, 1, 170) row = [] for m in maps(): lo, two = c_floor(met, m, 110), c_lo2(met, m, depth=110) ov = c_overlap(met, m, 110) far += not lo <= two <= ov row.append(f"x{m} {lo}/{two}/{ov}") print(f" {name:20s} c_lo/c_lo2/c_ov, depth 110 " + " ".join(row)) check("e - 2 and the random alpha: c_lo <= c_lo2 <= c_ov(0, 1)", far == 0) # ------------------------------------------------------------ P9(c) the limit def subtree_ok(met, m, c, t, L, plant=False): """The pinned subtree at level t, lookahead c, read L levels: the target m X_i inside the committed window W_i at i = 0 .. L - 1, the opponent's digit d_(j+i-1) then the reader's e_(t+i) at i >= 1. plant reads R' as d theta + I_(K+1).""" j = t + c + 1 x0 = zero_cyl(met, j) if not _inside((m * x0[0], m * x0[1]), zero_cyl(met, t + 1)): return False if L == 1: return True memo = {} def win(i, rel, prevzero): # rel = m (sum d theta) - (sum e theta): the target's offset # against the window's key = (i, rel, prevzero) if key in memo: return memo[key] K = j + i - 1 thK, thK1 = met.theta(K), met.theta(K + 1) top = met.a[K + 1] if prevzero else met.a[K + 1] - 1 ok = True for d in range(top + 1): r = zero_cyl(met, K + 1) if d == 0 or plant else \ _hull(-thK1, -thK - thK1) base = rel + m * d * thK lv = t + i win_lv = zero_cyl(met, lv + 1) if not any(_inside((base + m * r[0] - e * met.theta(lv), base + m * r[1] - e * met.theta(lv)), win_lv) and (i == L - 1 or win(i + 1, base - e * met.theta(lv), d == 0)) for e in range(met.cap(lv) + 1)): ok = False break memo[key] = ok return ok return win(1, 0, True) def c_level(met, m, L, ts, top, plant=False): """1 + the largest c below top at which the L-level subtree fails at some level of ts, and whether it passes at top - 1.""" ok = [all(subtree_ok(met, m, c, t, L, plant) for t in ts) for c in range(top)] return 1 + max([c for c in range(top) if not ok[c]], default=-1), ok[-1] class PinGame(Game): """The game built from the pinned states P_t alone: the branch (0, 0), the quotients a_(t+1) .. a_(t+c+1), the pending digits all 0.""" def __init__(self, src, m, look, ts): self.ts = ts super().__init__(src, m, 0, 1, look) def initial(self): per, c = self.src.period, self.look p = len(per) return [((self.pack(0, 0),), tuple(per[(k - 1) % p] for k in range(t + 1, t + c + 2)), (t + c + 1) % p, (0,) * c, True, t == 0, True) for t in self.ts] def section_pinlimit(grid): print("== P9(c) the pinned limit at (0, 1): c_L, c_inf and c_zero " "against c_saf") LMAX = 14 if FULL else 10 wide = (6, 7, 8, 9) if FULL else () cells = k1 = k2 = ctl1 = ctl2 = sand = nsand = movebad = 0 gridoff = ngrid = planted = plim = nplim = hit = lose_all = 0 stops = [] for name, per in PERIODIC: met = Metric(numeration(name, per), 0, 1, 120) p = len(per) # the normalized geometry repeats with the period: two periods read ts = [t for t in pin_levels(met, 24) if 1 <= t <= 2 * p] src = Source(period=per) row = [] for m in maps() + wide: zvec = pvec = "" saf = losing = None for c in range(13): g = Game(src, m, 0, 1, c) g.solve(False) zi = g.start_state([0] * (c + 2), [per[k % p] for k in range(c + 2)]) zvec += "T" if zi in g.W else "F" wins = g.wins lost = sum(i not in g.W for i in g.init) total = len(g.init) del g pg = PinGame(src, m, c, list(range(1, 2 * p + 1))) pg.solve(False) pvec += "T" if all(i in pg.W for i in pg.init) else "F" if wins: movebad += sum( [e for e, (_nz, succ) in pg.trans[i].items() if all(j in pg.W for j in succ)] != [0] for i in pg.init) del pg saf = c break del pg losing = (lost, total) cells += 1 if (name, m, 0, 1) in grid: ngrid += 1 gridoff += saf != grid[(name, m, 0, 1)][0] one, two = c_lo2(met, m, False), c_lo2(met, m) got = [c_level(met, m, L, ts, saf + 2) for L in range(1, LMAX + 1)] cs = [x for x, _ok in got] ctl1 += cs[0] != one ctl2 += cs[1] != two planted += c_level(met, m, 2, ts, 30, plant=True)[0] != two pin = 1 + max([c for c, v in enumerate(pvec) if v == "F"], default=-1) if m in maps(): nplim += 1 plim += c_level(met, m, LMAX, ts, saf + 2, plant=True)[0] != pin lim = cs[-1] stops.append(cs.index(lim) + 1) zero = 1 + max([c for c, v in enumerate(zvec) if v == "F"], default=-1) k1 += (not all(ok for _x, ok in got) or max(cs) > saf or pin > saf) k2 += (lim != pin) + (zero != pin) if two == saf: nsand += 1 sand += pin != saf hit += pin == saf lose_all += losing is not None and losing[0] == losing[1] row.append(f"x{m} {lim}/{pin}/{saf}") print(f" {name:20s} " + " ".join(row)) print(f" (lim c_L / c_inf / c_saf) c_L stops at L = {sorted(set(stops))}" f" of {LMAX}; c_inf = c_saf at {hit} of {cells} cells; at c_saf - 1 " f"every pre-read loses at {lose_all} of {cells}") check("control: c_saf read here equals the grid's at (0, 1)", gridoff == 0, f"{gridoff} of {ngrid} off") check("control: L = 1 is the one-level bar and L = 2 is c_lo2", ctl1 + ctl2 == 0, f"{ctl1}, {ctl2} of {cells} off") check("control: c_inf = c_saf where c_lo2 = c_saf", sand == 0, f"{sand} of {nsand} off") check("control: at c_saf the pinned states' only winning move is 0", movebad == 0, f"{movebad} states") check("plant: R' read as d theta + I_(K+1) moves the L = 2 control " "and the limit off c_inf", planted > 0 and plim > 0, f"at {planted} of {cells} cells and {plim} of {nplim}") check("K1: c_L and c_inf at most c_saf", k1 == 0, f"{k1} cells") check("K2: lim c_L and c_zero equal c_inf", k2 == 0, f"{k2} disagreements") # ------------------------------------------------------------ P6 def section_universal(grid): print("== P6 the universal reader") rnd = random.Random(SEED + 1) pins = [] cells = [((1, 2), 2, 1, 1, 2)] if FULL: cells += [((1, 2, 3), 2, 1, 1, 2), ((1, 2), 3, 1, 1, 3), ((1, 2), 3, 2, 2, 2)] for alph, m, s, s0, want in cells: src = Source(alphabet=alph) t0 = time.time() c, g = least(src, m, s, s0, True, hi=want) tag = "{" + ", ".join(map(str, alph)) + "}" print(f" {tag:10s} x{m} ({s},{s0}): c_int {c} states " f"{len(g.states) if g else '-'} ({time.time() - t0:.0f} s)") check(f"{tag} x{m} at ({s}, {s0}) reads at exactly {want}", c == want) if c == 2: for name, per in PERIODIC: cell = grid.get((name, m, s, s0)) if cell and set(per) <= set(alph) and (m - 1) * max(per) > s: pins.append((name, m, s, s0, cell[1])) if g is None: continue alphas = [[a] * 400 for a in alph] alphas += [[rnd.choice(alph) for _ in range(400)] for _ in range(12)] bad = 0 for quots in alphas: w = Numeration("class member", quots) bad += certify(g, w, m, s, s0, N_CHECK // 2) check(f"certified at {len(alphas)} members", bad == 0, f"{bad} bad") if (alph, m) == ((1, 2), 2): g2 = Game(src, m, s, s0, want, scale=2) won = g2.solve(True) mx = my = 0 unflushed = seeds = 0 for quots in alphas[:6]: # the two constant alphas, four random w = Numeration("class member", quots) for n in range(N_CHECK // 4): out, fl, path = g2.read(w.digits(n), quots) if not fl: unflushed += 1 continue x_, y_, x0 = lineage(g2, path) mx, my = max(mx, x_), max(my, y_) seeds += x0 != m * w.digits(n)[0] check("at twice the box the flushing lineages stay in the box", won and mx <= g.bx and my <= g.by and unflushed == seeds == 0, f"largest |g|, |h| = {mx}, {my} against ({g.bx}, {g.by}), " f"6 members, n < {N_CHECK // 4}, {unflushed} unflushed") del g2 del g print(f" the pin, grid alphas of a class won at 2 with a quotient " f"above s/(m - 1): {pins}") check("the pin: c_int is 2 at each of them", pins and all(c == 2 for *_, c in pins)) if not FULL: return print("== P6 the periodic members of {1, 2} for x 3 at (1, 1)") necks = necklaces((1, 2), 8) off = [] for per in necks: c, _g = least(Source(period=per), 3, 1, 1, True, hi=3) if c != 2: off.append((per, c)) check("every purely periodic alpha of primitive period <= 8 reads " "at 2", not off, f"{len(necks)} alphas (every rotation of " f"{len(set(min(tuple(p[i:] + p[:i]) for i in range(len(p))) for p in necks))}" f" words), off: {off}") def necklaces(alph, top): out = [] for P in range(1, top + 1): seen = set() for k in range(len(alph) ** P): word = [] for _ in range(P): k, r = divmod(k, len(alph)) word.append(alph[r]) rots = [tuple(word[i:] + word[:i]) for i in range(P)] if len(set(rots)) < P or min(rots) in seen: continue seen.add(min(rots)) out.extend(rots) return out # ------------------------------------------------------------ main def main(): t0 = time.time() section_ranges() section_controls() section_tear() cov = section_completion() section_floors() grid = section_grid(cov) section_digitwise() section_band() section_owed(grid) section_cone(grid) section_cylinder(grid, cov) section_pinned(grid) section_pinlimit(grid) section_universal(grid) n_ok = sum(CHECKS) print(f"\n{n_ok} of {len(CHECKS)} checks passed " f"({time.time() - t0:.1f} s{', full' if FULL else ''})") sys.exit(0 if n_ok == len(CHECKS) else 1) if __name__ == "__main__": main()