"""fixedstart.py -- a trip of the element machine that starts from one state on every supply waits at least 2 + ceil(log2(C'/s)) to read whether its newest modulus is coprime to the deep ones, and a correct reader meeting that hypothesis exists, so the floor is not vacuous. 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). rreader.py answers each R-number M flat in B from bits its finite control carries across trips. Take instead the hypothesis H: the trip starts, on every supply, from one control state with each register b holding one fixed integer s_b on every window, its grow its first op and no other grow; s = max(1, max over b of |s_b|). Does H force a floor growing with C', and does any correct reader meet H? THE FLOOR (by hand, before the engine). No multiply. (1) Every op is one integer map at every window, so under H a register holds one integer x on every deep window all trip (the grow writes 0 there); the t-th op of the trip, the grow first, sees |x| <= 2^(t - 2) s, each add or sub at most doubling the largest value; a zero-test of r is true iff C' | x_r and the newest residue of r is 0. (2) A COMPANION of a supply with C' > 1: the same M, the other answer, a deep lcm C'' > C'. Coprime: one deep modulus times the least prime p of M (C'' = C'p, clocks.py::section_lcm_wait's). Not coprime: the deep moduli replaced by the one modulus C'M + 1, coprime to M (C'' = C'M + 1). Under H both trips start alike, the newest window and every x agree while every test agrees, and for |x| < C', [C' | x] = [x = 0] = [C'' | x]. (3) So the two runs agree until a test of some |x| >= C' differs, and the answers differ; on every supply with C' > s the answer waits at least 2 + ceil(log2(C' / s)). With multiply, |x| <= max(2, s)^(2^(t - 2)), a floor of log2 log2 C' less a constant. (4) H is needed: rreader.py's bits come from earlier trips, and with 2 in R it answers M = 2 in one count at every B, below the floor once C' is large. THE H-READER (written before the engine). Registers ONES (1 on every window) and the rest 0 on every window at each trip's start: s = 1. A MUL of X by an aligned counter K (the same value k at every window) is Y := X, C := K - ONES, then while not zero(C): X := X + Y, C := C - ONES; it runs (k - 1) mod L adds, L the lcm of every modulus, and leaves X k at every window: a counter that wraps still multiplies right. grow F; DEEP := ONES (1 deep, 0 newest); ONES := ONES + F. MC := 0, T := 0; repeat MC := MC + ONES, T := T + F until zero(T): MC = M at every window. Q := DEEP, R := DEEP, DC := 0, W := 0; then per step d = 1, 2, ...: DC := DC + ONES, W := W + F (d at every window, d on the newest); the unit test (coprime.py's): V := 0, T := 0; repeat V := V + W, T := T + F until zero(V); unit := zero(T) (V first zero at k = M / gcd(d, M), T zero iff k = M); MUL R by MC; if unit: MUL Q by DC, MUL R by DC; if zero(Q): answer True; if zero(R): answer False. Close: clear every register but ONES. On the deep windows Q = prod of the d' <= d with gcd(d', M) = 1 and R = Q M^d, both 0 on the newest; zero(Q) iff C' | Q. If a prime q divides M and C', no factor of Q carries q: Q never vanishes, and R does once each p^e of C' with p not dividing M divides Q and d is at least each exponent of the rest. If gcd(M, C') = 1, R vanishes with Q and is tested after it, and Q vanishes by d = M d1, d1 the least d with C' | d!: for p^e of C', p not dividing M, the d' = p^a u <= M d1 with gcd(u, M) = 1 number at least floor(d1 / p^a) for each a, so v_p(Q) >= v_p(d1!) >= e. With no deep window Q = 0 at d = 1: True. THE COUNT (by hand). Before the steps: grow, DEEP, ONES 3; the measure 2 + 3M; Q, R, DC, W 4. A step: 2 + (3 + 3M/gcd(d, M)) + 3M + unit 6(1 + (d - 1) mod L) + 2 tests; the last step one test less when it answers True. With D the answering d: wait = 9 + 3M + sum over d <= D of (7 + 3M/gcd(d, M) + 3M + 6 [gcd(d, M) = 1](1 + (d - 1) mod L)) - [answer True]. Registers: ONES DEEP F MC T Q R DC W V Y C, 12. PREDICTIONS (frozen before the engine). P1 the H-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; section_random's 40 draws, seed 1668, moduli 2 .. 40, g = 1 .. 25) and on the supply 16, 3. P2 H at every trip start of P1: ONES 1 at every window, every other register 0 at every window, one control state. P3 every wait equals THE COUNT's closed form, D read off the integers; 12 registers. P4 every wait is at least the floor 2 + ceil(log2 C') (s = 1) where C' > 1, printed with log2 C' and the wait at the largest g. P5 THE CONTROL: at every trip of coprime.py's g + 1 and primes runs to g = 12 and of the first 10 random draws to g = 15, the companion run under the H-reader (from its own first window) with a shadow of each register's one deep integer: H holds at the companion's trip start, its answer differs, and the first op where the two traces differ is a zero-test whose shadow |x| is at least C' (both runs carry one x), every earlier test's |x| below C' or agreeing. P6 (a print) rreader.py with R = {2, 3} at M = 2 over the odd deep moduli 3 .. B, B in {9, 17, 33, 39}: its wait against the floor 2 + ceil(log2 C') a reader meeting H owes. CONTROLS, read before any verdict. C1 coprime.py's Reader on section_random's draws: every answer the gcd's (the engine and the run harness). C2 the shadow: at every test of pre's last trip, the one the companion races, the companion's uncounted, every deep residue of the tested register is its shadow mod that window's modulus. PLANTS. (a) R multiplied by every d and never by M (R = d!, the sketch that stops at the first zero of d!): on 16, 3 it answers False at d = 6 (720 = 16 45; Q = 40), must break P1. (b) the companion given M + 1 in place of M: its traces differ first at a test of |x| = 0 on the measure, must break P5's first-difference check. KILL (frozen). Printed: the count of trips off in P1, P2, P3, P4, P5, and of the plants' breaks. Fires if any of P1 .. P5 is off at any trip, or plant (a) breaks no P1 answer, or plant (b) breaks no P5 pair. ADDED LATER (frozen before its engine), a plant that can fail and a print. (c) the companion given one deep modulus C'' < C', the other answer kept: where M is coprime to C', the least prime p of M; where not, the least prime q not dividing M; a pair counted only where C'' < C'. A test of C'' <= |x| < C' may now differ first, so the plant breaks P5's check at some pairs and not at others. By hand: coprime, every test before d = 1's zero(R) agrees (T, V and W are 0 on the deep windows, a counter's test needs its newest residue 0 and so x = 0), Q = 1 there, and zero(R) at |x| = M differs: a break iff M < C'. Not coprime: the pre run answers at its own R test, |x| >= C', if its D < q; else the companion's Q first vanishes mod q at d = q (a counter wraps only past lcm(q, M) >= q), so the first difference is zero(Q) at d = q, |x| the product U of the units up to q: a break iff U < C'. Printed: the pairs counted, the breaks, and the pairs off this hand rule. (P3b) the largest D/B over P1's trips, B the largest deep modulus: at most 1, READING's answering d at most B. KILL, ADDED. Fires also if plant (c) breaks no pair, or any pair is off the hand rule, or P3b exceeds 1. A CHANGE TO THE FROZEN DESIGN, named: the not-coprime companion C'M + 1 is measured by unit steps on its own first trip (C'M + 1 near 5 10^6 at g = 12 on g + 1), and the first run met the 600 s clock there. It is now the primes not dividing M, taken upward from 2 until their product exceeds C': coprime to M, C'' > C', every window small. THE FLOOR's (2) holds for any companion with the same M, the other answer and C'' > C'. P5's "its answer differs" is read as the companion's gcd answer; its run stops at the first difference. P4 prints the floor, not log2 C'. FINDINGS (entered after the run, from its printed output). C1 coprime.Reader on the draws: 1000 trips, 0 off. P1 1061 trips, 0 answers off. P2 0 trip starts off H. P3 every wait and D the count's, 0 off; 12 registers, the list's. P4 0 waits below 2 + ceil(log2 C'). At g = 30: g + 1 (M = 32, B = 31) floor 49, wait 6880, D = 31, False; primes (M = 127, B = 113) floor 157, wait 125932, D = 113, True; 16, 3: floor 6, wait 367, D = 8, True. C2 178048 tests, 0 shadows off a deep residue. P5 174 pairs, 0 off. At every printed pair the first difference is the last op of the trip, the answering test: g + 1 at g = 1, 6, 12 (C' = 2, 420, 360360) first differ at op 84, 471, 1323 of 85, 472, 1324, the first tested |x| >= C' at op 34, 209, 517 (ops counted from 0, the floor 3, 11, 21); primes at g = 12, C' = 7420738134810, op 13709 of 13710, the first |x| >= C' at op 2070, floor 45. P6 rreader.py at R = {2, 3}, M = 2: wait 20 at B = 9, 17, 33, 39, against the floor 11, 22, 45, 50 a reader meeting H owes: below it from B = 17 on. B (a) R = d!: 3 answers off, (draw 23, g = 1, M = 10), (draw 38, g = 1, M = 10), (16, 3). (b) the companion at M + 1: 174 of 174 pairs break the check, a plant caught by construction (the measure's test of T, 0 on every deep window, differs first). (c), added: 169 pairs with C'' < C', 168 break the check (coprime 38 of 39, not coprime 130 of 130), 0 off the hand rule; the one held is draw 6 at g = 1, M = 36, C' = 31, C'' = 2, its first difference at |x| = 36 >= C'. P3b: the largest D/B is 1. K KILL MISSES. READING. Under H the deep side costs at least 2 + ceil(log2(C' / s)), by the proof above, and the H-reader makes it a floor on a correct reader, not on an empty class: s = 1, every answer the gcd's, and the two companions' traces agree up to the first difference, a test of some |x| >= C'. The first difference is the answering test at 90 of the 174 pairs and an earlier test at 84 (P5's print, added after the run). The H-reader waits far above the floor (6880 against 49, 125932 against 157 at g = 30), O(B(B + M)), the answering d at most B (each p^e of C' is at most B); whether a reader meeting H waits o(B^2) at fixed M is the open upper side (O(log C') is ruled out at C' = 2 by the newest side's sqrt(N) floor). Without H the floor fails: rreader.py's 20 at M = 2 sits below it from B = 17. RUN RECORD. 14 checks, 19.4 s, peak commit 13.5 MB (13.6 MB through the gate) under a memory cap (11 checks, 16.1 s, 11.7 MB before plant (c) and P3b); the first run, with the companion C'M + 1, stopped by the clock at 600 s. """ import os import sys from fractions import Fraction from math import gcd sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import rreader # noqa: E402 from coprime import Counted, Reader, truth, lcm_all # noqa: E402 from supply import check, section, CHECKS # noqa: E402 REGS = {"ONES", "DEEP", "F", "MC", "T", "Q", "R", "DC", "W", "V", "Y", "C"} class Diverged(Exception): pass class Traced(Counted): """coprime.py's Counted with H read at each trip start, a shadow of each register's one deep integer, and an optional trace checked op by op against a reference trace.""" def __init__(self, supply): super().__init__(supply) self.shadow = {} self.trace = None self.ref = None self.c2 = [0, 0] def h_holds(self): for r, v in self.R.items(): want = {w: 1 for w in range(len(self.m))} if r == "ONES" else {} if v != want: return False return True def start(self, record, ref): self.shadow = {"ONES": 1} self.trace = [] if record or ref is not None else None self.ref = ref def log(self, item, x=None): if self.trace is None: return i = len(self.trace) self.trace.append((item, x)) if self.ref is not None: if i >= len(self.ref) or self.ref[i] != (item, x): raise Diverged(i) def grow(self, into): super().grow(into) self.shadow[into] = 0 self.log(("grow", into)) def op(self, d, a, b, sign): super().op(d, a, b, sign) self.shadow[d] = self.shadow.get(a, 0) + sign * self.shadow.get(b, 0) self.log(("op", d, a, b, sign)) def copy(self, d, a): super().copy(d, a) self.shadow[d] = self.shadow.get(a, 0) self.log(("copy", d, a)) def clear(self, d): super().clear(d) self.shadow[d] = 0 self.log(("clear", d)) def zero(self, r): z = super().zero(r) x = self.shadow.get(r, 0) if self.trace is not None: v = self.reg(r) self.c2[1] += 1 self.c2[0] += any(v.get(w, 0) != x % self.m[w] for w in range(len(self.m) - 1)) self.log(("zero", r, z), abs(x)) return z class HReader: """THE H-READER: no state across trips but ONES, one control state at every trip start (trip() carries no variable across calls).""" def __init__(self, supply, plant=None): self.E = Traced(supply) self.plant = plant self.h_off = 0 def mul(self, X, K): E = self.E E.copy("Y", X) E.sub("C", K, "ONES") while not E.zero("C"): E.add(X, X, "Y") E.sub("C", "C", "ONES") def trip(self, record=False, ref=None): E = self.E self.h_off += not E.h_holds() E.start(record, ref) start = E.units E.grow("F") E.copy("DEEP", "ONES") E.add("ONES", "ONES", "F") E.clear("MC") E.clear("T") while True: E.add("MC", "MC", "ONES") E.add("T", "T", "F") if E.zero("T"): break E.copy("Q", "DEEP") E.copy("R", "DEEP") E.clear("DC") E.clear("W") d = 0 while True: d += 1 E.add("DC", "DC", "ONES") E.add("W", "W", "F") E.clear("V") E.clear("T") while True: E.add("V", "V", "W") E.add("T", "T", "F") if E.zero("V"): break unit = E.zero("T") if self.plant != "a": self.mul("R", "MC") if unit: self.mul("Q", "DC") if unit or self.plant == "a": self.mul("R", "DC") if E.zero("Q"): ans = True break if E.zero("R"): ans = False break wait = E.units - start trace = E.trace E.trace = None for r in list(E.R): if r != "ONES": E.clear(r) return ans, wait, d, trace def predicted(ms): """THE COUNT: (wait, D) from the integers.""" deep, M = ms[:-1], ms[-1] Cp = lcm_all(deep) L = lcm_all(ms) wait = 9 + 3 * M Q = 1 d = 0 while True: d += 1 u = gcd(d, M) == 1 wait += 7 + 3 * M // gcd(d, M) + 3 * M if u: wait += 6 * (1 + (d - 1) % L) Q *= d if Q % Cp == 0: return wait - 1, d if Q * M ** d % Cp == 0: return wait, d def floor(ms): """2 + ceil(log2 C'), s = 1, where C' > 1.""" Cp = lcm_all(ms[:-1]) return 2 + (Cp - 1).bit_length() if Cp > 1 else None def run(ms, plant=None, record_last=False): """Every trip on ms: (g, prefix, answer, wait, D, trace), g >= 1.""" X = HReader(lambda i: ms[i], plant) out = [] for g in range(len(ms)): rec = record_last and g == len(ms) - 1 ans, wait, d, trace = X.trip(record=rec) out.append((g, ms[:g + 1], ans, wait, d, trace)) return out[1:], X def p1_supplies(): return rreader.p1_supplies() + [("16, 3", [16, 3])] def section_controls(): section("C1 coprime.py's Reader on section_random's draws") off = n = 0 for ms in rreader.draws(): X = Reader(lambda i, ms=ms: ms[i]) X.trip() for g in range(1, len(ms)): ans, _, _ = X.trip() off += ans != truth(ms[:g + 1]) n += 1 check("C1 every answer the gcd's", off == 0, f"{n} trips, {off} off") def section_p1(): section("P1 .. P4 the H-reader on coprime.py's three runs and 16, 3") off = h = cnt = low = n = 0 first = [] names = set() tops = [] db = (0, None) for name, ms in p1_supplies(): out, X = run(ms) h += X.h_off names |= X.E.names for g, pre, ans, wait, d, _ in out: n += 1 if ans != truth(pre): off += 1 first.append((name, g)) cnt += (wait, d) != predicted(pre) f = floor(pre) low += f is not None and wait < f db = max(db, (Fraction(d, max(pre[:-1])), (name, g))) if name in ("g + 1", "primes", "16, 3"): g, pre, ans, wait, d, _ = out[-1] tops.append((name, g, pre[-1], max(pre[:-1]), floor(pre), wait, d, ans)) check("P1 every answer is the gcd's", off == 0, f"{n} trips, {off} off {first[:3]}") check("P2 H at every trip start", h == 0, f"{h} starts off") check("P3 every wait and D is THE COUNT's", cnt == 0, f"{cnt} off") check("P3 the 12 registers", names == REGS, f"{len(names)} used: {sorted(names - REGS)} extra, " f"{sorted(REGS - names)} missing") check("P4 every wait at least 2 + ceil(log2 C')", low == 0, f"{low} below") check("P3b the largest D/B is at most 1", db[0] <= 1, f"D/B = {db[0]} = {float(db[0]):.4f}, one at {db[1]}") for name, g, M, B, f, wait, d, ans in tops: print(f" {name} g = {g}: M = {M}, B = {B}, floor {f}, " f"wait {wait}, D = {d}, answer {ans}") return off + h + cnt + low + (db[0] > 1) def companion(pre): """THE FLOOR (2)'s companion: the same M, the other answer.""" deep, M = pre[:-1], pre[-1] if truth(pre): p = next(q for q in range(2, M + 1) if M % q == 0) return [deep[0] * p] + deep[1:] + [M] Cp, ps, q = lcm_all(deep), [], 2 while lcm_all(ps) <= Cp: if M % q and all(q % p for p in range(2, q)): ps.append(q) q += 1 return ps + [M] def pair(pre, comp): """The last trip of pre against comp's, the companion stopped at the first op where its trace leaves pre's.""" out, X = run(pre, record_last=True) g, _, ans, wait, d, trace = out[-1] Y = HReader(lambda i: comp[i]) for _ in range(len(comp) - 1): Y.trip() i = None try: Y.trip(ref=trace) except Diverged as e: i = e.args[0] Cp = lcm_all(pre[:-1]) big = next((k for k, (it, x) in enumerate(trace) if it[0] == "zero" and x >= Cp), None) yt = Y.E.trace ok = (i is not None and i < len(trace) and trace[i][0][0] == "zero" and yt[i][0][:2] == trace[i][0][:2] and yt[i][1] == trace[i][1] and trace[i][1] >= Cp and Y.h_off == 0 and X.h_off == 0 and truth(comp) != truth(pre)) dx = trace[i][1] if i is not None and i < len(trace) else None return ok, i, big, Cp, wait, X.E.c2, dx def p5_trips(): for name, ms in rreader.p1_supplies()[:2]: for g in range(1, 13): yield name, g, ms[:g + 1] for k, ms in enumerate(rreader.draws()[:10]): for g in range(1, 16): yield f"draw {k}", g, ms[:g + 1] def section_p5(plant=None): section("P5 THE CONTROL: companions under the H-reader" + (" (plant b: the companion at M + 1)" if plant else "")) bad = n = last = 0 c2 = [0, 0] rows = [] for name, g, pre in p5_trips(): comp = companion(pre) if plant == "b": comp = comp[:-1] + [comp[-1] + 1] ok, i, big, Cp, wait, cc, _ = pair(pre, comp) n += 1 bad += not ok last += i == wait - 1 c2[0] += cc[0] c2[1] += cc[1] if name in ("g + 1", "primes") and g in (1, 6, 12): rows.append((name, g, Cp, floor(pre), big, i, wait)) if plant: print(f" {bad} of {n} pairs break the first-difference check") return bad check("C2 the shadow is every deep residue at every test", c2[0] == 0, f"{c2[1]} tests, {c2[0]} off") check("P5 every pair: H, the other answer, the first difference a " "test of |x| >= C'", bad == 0, f"{n} pairs, {bad} off") print(f" {last} of {n} pairs first differ at the answering test") for name, g, Cp, f, big, i, wait in rows: print(f" {name} g = {g}: C' = {Cp}, floor {f}, first tested " f"|x| >= C' at op {big}, first difference at op {i}, " f"wait {wait}") return bad def section_p6(): section("P6 rreader.py, R = {2, 3}, at M = 2 over the odd deep moduli") for B in (9, 17, 33, 39): ms = list(range(3, B + 1, 2)) + [2] out, _ = rreader.run((2, 3), ms) print(f" B = {B}: wait {out[-1][3]}, floor owed under H " f"{floor(ms)}") def small_companion(pre): """Plant (c): one deep modulus C'' < C', the other answer kept; None where no such C'' is this one.""" deep, M = pre[:-1], pre[-1] Cp = lcm_all(deep) if truth(pre): c = next(q for q in range(2, M + 1) if M % q == 0) else: c = next(q for q in range(2, 10 ** 6) if M % q and all(q % p for p in range(2, q))) return [c, M] if c < Cp else None def hand_rule(pre, comp): """Plant (c)'s hand rule: (the first difference's |x|, or None for 'pre's answering test, |x| >= C''), and whether it breaks P5.""" deep, M = pre[:-1], pre[-1] Cp = lcm_all(deep) if truth(pre): return M, M < Cp q = comp[0] if predicted(pre)[1] < q: return None, False U = 1 for d in range(1, q + 1): if gcd(d, M) == 1: U *= d return U, U < Cp def section_plant_c(): section("B plant (c): the companion with one deep modulus C'' < C'") n = brk = offrule = 0 split = {True: [0, 0], False: [0, 0]} examples = [] for name, g, pre in p5_trips(): comp = small_companion(pre) if comp is None: continue ok, i, big, Cp, wait, _, dx = pair(pre, comp) n += 1 broke = dx is not None and dx < Cp brk += broke split[truth(pre)][0] += 1 split[truth(pre)][1] += broke want, wbreak = hand_rule(pre, comp) good = (broke == wbreak and (dx == want if want is not None else i == wait - 1 and dx >= Cp)) offrule += not good if not broke or sum(e[-1] for e in examples) < 3: examples.append((name, g, pre[-1], Cp, comp[0], dx, broke)) print(f" {n} pairs counted (C'' < C'), {brk} break P5's check; " f"coprime {split[True][1]} of {split[True][0]}, not coprime " f"{split[False][1]} of {split[False][0]}; {offrule} off the " f"hand rule") for name, g, M, Cp, c, dx, broke in examples: print(f" {name} g = {g}: M = {M}, C' = {Cp}, C'' = {c}, first " f"difference at |x| = {dx}, {'a break' if broke else 'held'}") return n, brk, offrule def section_plant_a(): section("B plant (a): R = d!, never multiplied by M") bad = [] for name, ms in p1_supplies(): out, _ = run(ms, plant="a") bad += [(name, g, pre[-1]) for g, pre, ans, *_ in out if ans != truth(pre)] print(f" {len(bad)} answers off, first {bad[:3]}; at 16, 3: " f"{[b for b in bad if b[0] == '16, 3']}") return len(bad) def main(): section_controls() if not all(CHECKS): print("\ncontrols fail: no verdict") return 1 off = section_p1() bad = section_p5() section_p6() pa = section_plant_a() pb = section_p5(plant="b") nc, pc, rc = section_plant_c() check("Ba plant (a) breaks P1", pa > 0, f"{pa} off") check("Bb plant (b) breaks P5", pb > 0, f"{pb} pairs") check("Bc plant (c) breaks P5 at some pair, holds at others", 0 < pc < nc, f"{pc} of {nc}") check("Bc every pair on the hand rule", rc == 0, f"{rc} off") fired = (off > 0 or bad > 0 or pa == 0 or pb == 0 or pc == 0 or rc > 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())