"""evenbit.py -- the element machine without multiply answers every newest modulus M = 2^t in 4t + 2 unit ops whatever the deep moduli are, by keeping [C' even] in its finite control. QUESTION. coprime.py's machine: registers over windows, add, sub, copy, clear, GROW naming its register, a zero-test per register, no multiply, no nonzero constant. A fixed program reads, after each grow, whether the newest modulus M is coprime to the deep moduli (C' their lcm, B their largest). coprime.py's Reader waits O(B(B + M)), touching every d <= B. Must any correct reader's wait grow with B (a floor in B alone)? And does the deep side set a floor near log2 of the part of C' coprime to M when every deep window holds one integer? THE CONSTRUCTION (written before the engine). The PARITY READER is coprime.py's Reader with one finite-control bit EVEN = [C' even] and a lockstep before its d loop. After the grow and ONES := ONES + F: D := F, S := 0; then per step j = 1, 2, ...: D := D + D; if zero(D): answer [not EVEN], stop the trip; S := S + F; if zero(S): leave the lockstep, run the plain d loop. F, D and S are 0 on every deep window, and on the newest D = 2^j, S = j (mod M). So zero(D) at step j iff M | 2^j, iff M = 2^t and j >= t; zero(S) at step j iff M | j. D is tested first, so for M = 2^t (t < M at every M >= 2) the lockstep stops at j = t, and at any other M at j = M with D never zero. Then gcd(2^t, C') = 1 iff C' is odd, so [not EVEN] is the answer. The bit: M is even in the power branch, and in the other branch M's parity is j's at exit, a toggle per step; after the answer EVEN := EVEN or [M even], which makes it [C' even] for the next trip, whose deep moduli are these and M. A change from the first plan, named: the plan read M's parity in the upkeep while it measures M; reading it in the lockstep costs no op and leaves coprime.py's upkeep untouched. The upkeep runs after either branch as coprime.py's (it needs F, ONES, DEEP, BC only). THE COUNT (by hand, read off the construction). Power branch, M = 2^t: grow 1, ONES 1, D and S 2, t - 1 full steps of 4, the last step's add and test 2: wait = 4t + 2. full = 1 + wait + upkeep = 4t + 3 + 3M + 3B + 5 max(B, M). Other M: the lockstep 2 + 4M, then the plain reader's ops after its grow and ONES: wait = coprime.counted(B, M)[0] + 4M + 2, and full = coprime.counted(B, M)[1] + 4M + 2. Registers: coprime.py's 14 and D, 15. THE DEEP SIDE. In the power branch every register the wait touches (DEEP, F, ONES, D, S) holds 0 or 1 on every deep window, and the wait 4t + 2 does not see C'. On odd deep moduli 3 .. B the part of C' coprime to 2^t is C' itself, lcm of the odd numbers to B, log2 47.25 at B = 39, against a wait of 6 at M = 2. PREDICTIONS (frozen before the engine). P1 the parity reader's answer equals [gcd(M, C') = 1] at every trip of coprime.py's three runs: m_g = g + 1 and the primes, g = 1 .. 30, and section_random's 40 draws (seed 1668, moduli 2 .. 40, g = 1 .. 25). P2 THE SWEEP. Deep moduli E_B = 2 .. B (C' even) and O_B = the odd numbers 3 .. B (C' odd), B in {3, 5, 9, 17, 33, 39}, then M = 2^t, t = 1 .. 10: the wait is 4t + 2 in every cell, the same at every B; the answer is False on E_B and True on O_B. Beside it, the plain reader's wait on the same cells, which grows with B (a print). P3 at every trip of P1 the wait and the full cycle equal THE COUNT's closed forms, power branch or not; 15 registers. P4 (a print) at every sweep cell the wait is at least the proved floor 2 + ceil(log2 M) = t + 2; log2 C' printed per B, and at t = 1 (wait 6) on O_B the wait sits below log2 C' from B = 9 on (log2 C' by hand: 1.58, 3.91, 8.30, 19.55, 42.04, 47.25). CONTROLS, read before any verdict. C1 coprime.py's Reader on section_random's draws: every answer the gcd's and every wait and full cycle coprime.counted's, the engine and the count convention this script leans on. C2 the sweep's supplies through the plain Reader: answers False on E_B, True on O_B at every t. PLANT, must break P1: (a) EVEN frozen at False (never set): on m_g = g + 1 at g = 2 (M = 4, deep 2, 3) it answers True where the gcd says False. (b) the D test removed: the answers stay right and P2's wait breaks at every cell (a plant on the wait check). KILL (frozen). Printed: per t, the parity waits across the twelve deep supplies. Fires if any answer of P1 or P2 differs from the gcd, if at any t the twelve waits are not all 4t + 2, or if plant (a) breaks no answer or plant (b) leaves any P2 wait at 4t + 2. FINDINGS (entered after the run, from its printed output). C1 coprime.Reader on the draws: 1000 trips, 0 answers off, 0 counts off. C2 the sweep through it: 0 off of 120. P1 1060 trips, 134 through the power branch, 0 answers off. P3 every wait and full cycle is THE COUNT's, 0 off; 15 registers. P2 0 sweep answers off; at every t = 1 .. 10 the twelve waits are all 4t + 2 (6, 10, ..., 42). The plain reader on the same cells: at t = 1, 54, 93, 189, 453, 1269, 1674 for B = 3 .. 39 (E and O the same, counted(B, M) seeing only B and M); at t = 10, 7719 to 83193. P4 no wait below t + 2; log2 C' on O_B 1.58, 3.91, 8.30, 19.55, 42.04, 47.25, so the wait 6 at t = 1 is below it at B = 9, 17, 33, 39. B (a) EVEN frozen: 131 answers off, first (g + 1, g = 2, M = 4), (g + 1, 6, 8), (g + 1, 14, 16). (b) the D test removed: 0 sweep waits at 4t + 2, 0 answers off. K KILL MISSES. READING. A floor in B alone is false: at M = 2 the wait is 6 at every B. The front's last clause owes a hypothesis: the wait tests only D and S, 0 on every deep window (registers the wait does not touch keep earlier trips' residues there), and at t = 1 it sits below log2 C', the part coprime to M, at B = 9, 17, 33, 39 of the grid; the bit that answers was carried in the finite control from earlier trips, so a floor of that shape owes a hypothesis on what the control keeps. RUN RECORD. 12 checks, 14.1 s, peak commit 6.9 MB under a memory cap. """ import os import random import sys from math import log2 sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import coprime # noqa: E402 from coprime import Reader, truth, counted, lcm_all # noqa: E402 from supply import PRIMES, check, section, CHECKS # noqa: E402 REGS = coprime.REGS | {"D"} BS = (3, 5, 9, 17, 33, 39) TS = range(1, 11) class Parity(Reader): """coprime.py's Reader with EVEN = [C' even] in finite control and the doubling lockstep before its d loop.""" def __init__(self, supply, plant=None): super().__init__(supply) self.even = False self.pplant = plant self.branch = None def trip(self): E = self.E begin = E.units E.copy("DEEP", "ONES") start = E.units E.grow("F") E.add("ONES", "ONES", "F") E.copy("D", "F") E.clear("S") odd_steps = False # finite control: j mod 2 while True: E.add("D", "D", "D") if self.pplant != "b" and E.zero("D"): answer = not self.even wait = E.units - start if self.pplant != "a": self.even = True # M = 2^t is even self.branch = "pow" self.upkeep() return answer, wait, E.units - begin E.add("S", "S", "F") odd_steps = not odd_steps if E.zero("S"): break if self.pplant != "a" and not odd_steps: # M = j, j even self.even = True self.branch = "plain" answer = self.plain_loop() wait = E.units - start self.upkeep() return answer, wait, E.units - begin def plain_loop(self): """coprime.py's Reader.trip after its grow and ONES, its plant branches cut.""" E = self.E E.copy("X", "DEEP") E.clear("DC") E.copy("W", "F") stop = "BC" while True: E.clear("V") E.clear("S") while True: E.add("V", "V", "W") E.add("S", "S", "F") if E.zero("V"): break if E.zero("S"): E.copy("Y", "X") E.copy("TC", "DC") while not E.zero("TC"): E.add("Y", "Y", "X") E.sub("TC", "TC", "DEEP") E.copy("X", "Y") E.sub("T", "DC", stop) if E.zero("T"): break E.add("DC", "DC", "DEEP") E.add("W", "W", "F") return E.zero("X") def power(M): """t if M = 2^t, t >= 1, else None.""" t = M.bit_length() - 1 return t if M >= 2 and M == 1 << t else None def predicted(B, M): """THE COUNT: (wait, full) of the parity reader.""" t = power(M) if t is not None: w = 4 * t + 2 return w, 1 + w + 3 * M + 3 * B + 5 * max(B, M) w, f = counted(B, M) return w + 4 * M + 2, f + 4 * M + 2 def run(cls, ms, plant=None): """Every trip on the supply ms (a tail of 2s past it, never grown): (g, prefix, answer, wait, full, branch) for g = 1 .. len(ms) - 1.""" sup = (lambda i: ms[i] if i < len(ms) else 2) R = cls(sup, plant) if plant else cls(sup) R.trip() out = [] for g in range(1, len(ms)): ans, wait, full = R.trip() out.append((g, ms[:g + 1], ans, wait, full, getattr(R, "branch", None))) return out, R.E.names def draws(): """coprime.py::section_random's 40 draws, the same generator.""" rng = random.Random(1668) return [[rng.randint(2, 40) for _ in range(26)] for _ in range(40)] def p1_supplies(): return ([("g + 1", [g + 2 for g in range(31)]), ("primes", [PRIMES[g] for g in range(31)])] + [(f"draw {i}", ms) for i, ms in enumerate(draws())]) def deep(kind, B): return list(range(2, B + 1)) if kind == "E" else list(range(3, B + 1, 2)) def section_controls(): section("C controls: the plain reader on the draws and the sweep") off = miss = n = 0 for ms in draws(): out, _ = run(Reader, ms) for g, mm, ans, wait, full, _ in out: M, B = mm[-1], max(mm[:-1]) off += ans != truth(mm) miss += (wait, full) != counted(B, M) n += 1 check("C1 coprime.Reader on the draws: answers the gcd's, waits and " "full cycles coprime.counted's", off == 0 and miss == 0, f"{n} trips, {off} answers off, {miss} counts off") bad = 0 for kind in "EO": for B in BS: for t in TS: out, _ = run(Reader, deep(kind, B) + [2 ** t]) bad += out[-1][2] != (kind == "O") check("C2 the sweep through the plain reader: False on E_B, True on " "O_B", bad == 0, f"{bad} off of {2 * len(BS) * len(TS)}") def p1(plant=None): off = miss = n = npow = 0 first = [] names = set() for name, ms in p1_supplies(): out, nm = run(Parity, ms, plant) names |= nm for g, mm, ans, wait, full, br in out: M, B = mm[-1], max(mm[:-1]) if ans != truth(mm): off += 1 if len(first) < 3: first.append((name, g, M)) miss += (wait, full) != predicted(B, M) npow += br == "pow" n += 1 return off, miss, n, npow, first, names def section_answers(): section("P1, P3 the parity reader on coprime.py's three runs") off, miss, n, npow, first, names = p1() print(f" {n} trips, {npow} through the power branch") check("P1 every answer is the gcd's", off == 0, f"{off} off {first}") check("P3 every wait and full cycle is THE COUNT's", miss == 0, f"{miss} off") check("P3 the 15 registers", names == REGS, f"{len(names)} used: {sorted(names - REGS)} extra, " f"{sorted(REGS - names)} missing") return off def sweep(plant=None): """{(kind, B, t): (answer, parity wait, plain wait)}.""" cells = {} for kind in "EO": for B in BS: for t in TS: ms = deep(kind, B) + [2 ** t] pout, _ = run(Parity, ms, plant) cout, _ = run(Reader, ms) cells[kind, B, t] = (pout[-1][2], pout[-1][3], cout[-1][3]) return cells COLS = [(k, B) for k in "EO" for B in BS] def section_sweep(): section("P2, P4 the sweep: deep E_B = 2..B, O_B = odd 3..B; M = 2^t") cells = sweep() print(" parity wait by t (columns E_3 .. E_39, then O_3 .. O_39):") for t in TS: print(f" t={t:>2} 4t+2={4 * t + 2:>3} " + " ".join( f"{cells[k, B, t][1]:>3}" for k, B in COLS)) print(" the plain reader's wait on the same cells, t = 1 and t = 10:") for t in (1, 10): print(f" t={t:>2} " + " ".join( f"{cells[k, B, t][2]:>6}" for k, B in COLS)) print(" log2 C' on O_B: " + ", ".join( f"B={B} {log2(lcm_all(deep('O', B))):.2f}" for B in BS)) ans_off = sum(cells[k, B, t][0] != (k == "O") for k, B in COLS for t in TS) flat = [t for t in TS if {cells[k, B, t][1] for k, B in COLS} != {4 * t + 2}] under = sum(cells[k, B, t][1] < t + 2 for k, B in COLS for t in TS) below = [B for B in BS if cells["O", B, 1][1] < log2(lcm_all(deep("O", B)))] check("P2 every sweep answer: False on E_B, True on O_B", ans_off == 0, f"{ans_off} off") check("P2 at every t the twelve waits are all 4t + 2", flat == [], f"t off: {flat}") check("P4 every wait >= 2 + ceil(log2 M) = t + 2", under == 0, f"{under} under") check("P4 at t = 1 the wait is below log2 C' on O_B from B = 9 on", below == [9, 17, 33, 39], f"below at {below}") return ans_off, flat def section_plants(): section("B plants") off, _, _, _, first, _ = p1("a") print(f" (a) EVEN frozen at False: {off} answers off, first {first}") check("Ba the frozen bit breaks P1", off > 0, f"{off} off") cells = sweep("b") held = sum(cells[k, B, t][1] == 4 * t + 2 for k, B in COLS for t in TS) aoff = sum(cells[k, B, t][0] != (k == "O") for k, B in COLS for t in TS) print(f" (b) the D test removed: {held} sweep waits still 4t + 2, " f"{aoff} answers off") check("Bb the removed test breaks every P2 wait", held == 0, f"{held} held") return off, held def main(): section_controls() if not all(CHECKS): print("\ncontrols fail: no verdict") return 1 p1_off = section_answers() ans_off, flat = section_sweep() a_off, held = section_plants() fired = p1_off > 0 or ans_off > 0 or flat != [] or a_off == 0 \ or held > 0 print(f"\n KILL {'FIRES' if fired else 'MISSES'}") check("K the kill misses", not fired) print(f"\n{sum(CHECKS)}/{len(CHECKS)} checks pass") return 0 if all(CHECKS) else 1 if __name__ == "__main__": sys.exit(main())