"""rreader.py -- for a finite set R of primes, the element machine without multiply answers every newest modulus M that is an R-number in a wait linear in M's largest exponent, whatever the deep moduli are, by keeping [r | C'] for each r in R 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). evenbit.py answers every M = 2^t in 4t + 2 at every B. Does every finite R of primes carry the same: one reader answering every R-number M flat in B? If so, no single M carries a floor in B over every reader (R = the primes of M). THE CONSTRUCTION (written before the engine). L = the product of R. The R-READER is coprime.py's Reader with bits b_r = [r | C'], r in R, in its finite control (all False before the first grow, C' = 1) and a lockstep before its d loop. A MULTIPLY of register X by a constant c >= 2 is a copy Y := X and c - 1 adds X := X + Y (c ops); by c = 1 it is nothing (0 ops); m(c) is that cost. After the grow and ONES := ONES + F: D := F; D_r := F for each r in R; S := 0; then per step j = 1, 2, ...: multiply D by L; multiply each D_r by L/r; if zero(D): test every D_r, answer, stop the trip; S := S + F; if zero(S): leave the lockstep, run the plain d loop. Y, D, every D_r and S are multiples of F, 0 on every deep window; on the newest D = L^j, D_r = (L/r)^j, S = j (mod M). zero(D) at step j iff M | L^j, iff M is an R-number of largest exponent at most j; so for an R-number M it fires first at j0, M's largest exponent over R (j0 <= log2 M < M, so before S), and at any other M >= 2 never, the lockstep then leaving at j = M, the first j with M | j. At j0, (L/r)^j0 is a multiple of M iff r does not divide M: the other primes of M have exponent at most j0 in it and r has 0 in L/r. So D_r is nonzero iff r | M, and M is coprime to C' iff [not b_r] for every r with D_r nonzero; that AND is the answer. The bits: in the R-number branch b_r := b_r or [D_r nonzero]; in the other branch the finite control keeps j mod L, which at exit is M mod L, and b_r := b_r or [r | j]. The upkeep then runs as coprime.py's after either branch. THE COUNT (by hand, read off the construction). c := m(L) + the sum over r of m(L/r). Before the first step: grow, ONES, D, the |R| copies D_r, S: |R| + 4. A full step: c + 3 (the multiplies, three tests and adds). The last step of the R-number branch: c, zero(D), the |R| tests. R-number M: wait = |R| + 4 + (j0 - 1)(c + 3) + c + 1 + |R| = 2|R| + 2 + j0 (c + 3), full = 1 + wait + 3M + 3B + 5 max(B, M). R = {2, 3}: L = 6, c = 6 + 3 + 2 = 11, wait = 6 + 14 j0. R = {2, 3, 5}: L = 30, c = 30 + 15 + 10 + 6 = 61, wait = 8 + 64 j0. Other M: the lockstep before the plain reader's ops after its grow and ONES is |R| + 2 + M (c + 3): wait = counted(B, M)[0] + |R| + 2 + M (c + 3), full = counted(B, M)[1] + |R| + 2 + M (c + 3). At R = {2} this is not evenbit's count (D_2 is multiplied by 1, D by copy and add): wait 4 + 5 j0, not 4t + 2. Registers: coprime.py's 14 (Y among them, the multiply's copy), D and the |R| registers D_r: 15 + |R|. THE SWEEP'S FAMILIES. For T a subset of R and a cap in {9, 17, 33, 40}, deep = the d in 2 .. cap whose primes in R all lie in T (nonempty: 7 lies in every family at both R). Then C' has r in R as a factor iff r is in T, so the answer at an R-number M is [no prime of M lies in T]. B = the family's largest modulus. M runs over the R-numbers 2 .. 1024 (by hand 40 of them at R = {2, 3}; j0 from 1 to 10 at both R). PREDICTIONS (frozen before the engine), at R = {2, 3} and {2, 3, 5}. P1 the R-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: at every family, cap and R-number M, the answer is the family's rule and the wait is 2|R| + 2 + j0 (c + 3), the same at every family and cap at one j0 (flat in B, B to 40). P3 at every trip of P1 the wait and the full cycle equal THE COUNT's closed forms, R-number or not; 15 + |R| registers. P4 (a print) the plain reader's wait counted(B, 2)[0] at each family's B, against the R-reader's 2|R| + 2 + c + 3 at j0 = 1. 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 every sweep cell's gcd answer equals the family's rule (the family built as THE SWEEP'S FAMILIES says, read off truth()). PLANTS, each must break P1: (a) b_2 frozen at False (never set): on m_g = g + 1 at g = 2 (deep 2, 3; M = 4) it answers True where the gcd says False. (b) the D_r tests ignored by the answer, which is the AND over every r in R of [not b_r] (the bits still set from the tests): wrong wherever an R-number M misses a prime of R that divides C' and is coprime to C', as M = 2 after deep moduli 3, 5 (the gcd True, the bits False); "and is coprime to C'" added after the run. KILL (frozen). Printed: per R and per j0, the set of R-number waits over every sweep cell of that j0. Fires if any answer of P1 or P2 differs from the gcd, if at any (R, j0) that set is not exactly {2|R| + 2 + j0 (c + 3)}, if any P3 count is off, or if plant (a) or plant (b) breaks no P1 answer. FINDINGS (entered after the run, from its printed output). C1 coprime.Reader on the draws: 1000 trips, 0 answers off, 0 counts off. C2 0 sweep cells off the family's rule, of 3392. P1 R = {2, 3}: 1060 trips, 355 through the R-number branch, 0 answers off; R = {2, 3, 5}: 1060 trips, 541, 0 off. P3 every wait and full cycle is THE COUNT's, 0 off at both R; 17 and 18 registers, the list's. P2 R = {2, 3}: 40 R-numbers 2 .. 1024, j0 = 1 .. 10, 640 cells, B over them 7 to 40; at every j0 the waits are the one value 6 + 14 j0 (20, 34, ..., 146); 0 answers off. R = {2, 3, 5}: 86 R-numbers, 2752 cells, B 7 to 40, waits 8 + 64 j0 (72, 136, ..., 648); 0 off. P4 the plain reader's wait at M = 2, counted(B, 2), runs 138 at B = 7 to 1684 at B = 40; the R-reader's at j0 = 1 is 20 and 72. B (a) b_2 frozen: 146 and 157 answers off, first (g + 1, g = 2, M = 4). (b) the tests ignored: 7 and 22 off, first (g + 1, g = 1, M = 3: deep 2, the bits say False, the gcd True). K KILL MISSES. READING. For each finite R of primes one reader answers every R-number M in 2|R| + 2 + j0 (c + 3), j0 <= log2 M, at every B (by the construction; run at R = {2, 3} and {2, 3, 5}); so for each single M >= 2 the reader with R = the primes of M has a wait at M that does not see B. A floor in B owes uniformity over M: the open form is whether one reader can be flat in B at every M, where the lockstep's c + 3 per step grows with L, and every M not an R-number pays M (c + 3) before the plain reader runs. RUN RECORD. 17 checks, 14.4 s, peak commit 8.5 MB under a memory cap. """ import copy import os import random import sys from math import prod sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import coprime # noqa: E402 from coprime import Reader, truth, counted # noqa: E402 from supply import PRIMES, check, section, CHECKS # noqa: E402 RS = ((2, 3), (2, 3, 5)) CAPS = (9, 17, 33, 40) MMAX = 1024 def m(c): return 0 if c == 1 else c def consts(R): L = prod(R) return L, m(L) + sum(m(L // r) for r in R) def rname(r): return f"D{r}" class RReader(Reader): """coprime.py's Reader with b_r = [r | C'] in finite control and the L-power lockstep before its d loop.""" def __init__(self, supply, R, plant=None): super().__init__(supply) self.Rs = R self.L = prod(R) self.bits = {r: False for r in R} self.rplant = plant self.keep = True self.branch = None def mul(self, X, c): if c == 1: return E = self.E E.copy("Y", X) for _ in range(c - 1): E.add(X, X, "Y") def setbit(self, r, v): if v and not (self.rplant == "a" and r == 2): self.bits[r] = True def trip(self): E, R, L = self.E, self.Rs, self.L begin = E.units E.copy("DEEP", "ONES") start = E.units E.grow("F") E.add("ONES", "ONES", "F") E.copy("D", "F") for r in R: E.copy(rname(r), "F") E.clear("S") jmod = 0 # finite control: j mod L while True: self.mul("D", L) for r in R: self.mul(rname(r), L // r) jmod = (jmod + 1) % L if E.zero("D"): divides = {r: not E.zero(rname(r)) for r in R} if self.rplant == "b": answer = all(not self.bits[r] for r in R) else: answer = all(not self.bits[r] for r in R if divides[r]) wait = E.units - start for r in R: self.setbit(r, divides[r]) self.branch = "R" if self.keep: self.upkeep() return answer, wait, E.units - begin E.add("S", "S", "F") if E.zero("S"): break for r in R: self.setbit(r, jmod % r == 0) self.branch = "plain" answer = self.plain_loop() wait = E.units - start if self.keep: 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 (evenbit.py's Parity.plain_loop).""" 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 j0(M, R): """M's largest exponent over R if M is an R-number >= 2, else None.""" if M < 2: return None e = 0 for r in R: k = 0 while M % r == 0: M //= r k += 1 e = max(e, k) return e if M == 1 else None def predicted(R, B, M): """THE COUNT: (wait, full) of the R-reader.""" L, c = consts(R) j = j0(M, R) if j is not None: w = 2 * len(R) + 2 + j * (c + 3) return w, 1 + w + 3 * M + 3 * B + 5 * max(B, M) w, f = counted(B, M) extra = len(R) + 2 + M * (c + 3) return w + extra, f + extra def run(R, ms, plant=None): """Every trip on the supply ms (a tail of 2s, 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) X = RReader(sup, R, plant) X.trip() out = [] for g in range(1, len(ms)): ans, wait, full = X.trip() out.append((g, ms[:g + 1], ans, wait, full, X.branch)) return out, X.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 subsets(R): return [tuple(r for i, r in enumerate(R) if mask >> i & 1) for mask in range(1 << len(R))] def family(R, T, cap): return [d for d in range(2, cap + 1) if all(r in T for r in R if d % r == 0)] def rnumbers(R): return [M for M in range(2, MMAX + 1) if j0(M, R) is not None] def regs(R): return coprime.REGS | {"D"} | {rname(r) for r in R} def rule(T, M): return not any(M % r == 0 for r in T) def section_controls(): section("C controls: the plain reader on the draws; the families") off = miss = n = 0 for ms in draws(): X = Reader(lambda i, ms=ms: ms[i]) X.trip() for g in range(1, len(ms)): ans, wait, full = X.trip() mm = ms[:g + 1] 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 = cells = 0 for R in RS: for T in subsets(R): for cap in CAPS: dp = family(R, T, cap) for M in rnumbers(R): bad += truth(dp + [M]) != rule(T, M) cells += 1 check("C2 every sweep cell's gcd answer is the family's rule", bad == 0, f"{bad} off of {cells}") def p1(R, plant=None): off = miss = n = nR = 0 first = [] names = set() for name, ms in p1_supplies(): out, nm = run(R, 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(R, B, M) nR += br == "R" n += 1 return off, miss, n, nR, first, names def section_answers(R): section(f"P1, P3 R = {set(R)} on coprime.py's three runs") off, miss, n, nR, first, names = p1(R) print(f" {n} trips, {nR} through the R-number branch") check(f"P1 R = {set(R)}: every answer is the gcd's", off == 0, f"{off} off {first}") check(f"P3 R = {set(R)}: every wait and full cycle is THE COUNT's", miss == 0, f"{miss} off") check(f"P3 R = {set(R)}: the {15 + len(R)} registers", names == regs(R), f"{len(names)} used: " f"{sorted(names - regs(R))} extra, " f"{sorted(regs(R) - names)} missing") return off, miss def sweep(R): """{(T, cap, M): (answer, wait, B)}: each family's prefix run once, then one trip per M on a copy, its upkeep skipped (the wait alone is read; the full cycle is P3's).""" cells = {} for T in subsets(R): for cap in CAPS: dp = family(R, T, cap) box = {"M": 2} X = RReader(lambda i, dp=dp, box=box: dp[i] if i < len(dp) else box["M"], R) for _ in dp: X.trip() X.keep = False for M in rnumbers(R): box["M"] = M Y = copy.deepcopy(X) ans, wait, _ = Y.trip() assert len(Y.E.m) == len(dp) + 1 and Y.E.m[-1] == M cells[T, cap, M] = (ans, wait, max(dp)) return cells def section_sweep(R): L, c = consts(R) section(f"P2, P4 the sweep at R = {set(R)}: L = {L}, c = {c}") cells = sweep(R) ms = rnumbers(R) js = sorted({j0(M, R) for M in ms}) Bs = sorted({v[2] for v in cells.values()}) print(f" {len(ms)} R-numbers 2 .. {MMAX}, j0 = {js[0]} .. {js[-1]}; " f"{len(subsets(R))} families x {len(CAPS)} caps; B over the " f"cells: {Bs}") ans_off = sum(cells[k][0] != rule(k[0], k[2]) for k in cells) bad = [] for j in js: ws = sorted({v[1] for k, v in cells.items() if j0(k[2], R) == j}) want = 2 * len(R) + 2 + j * (c + 3) print(f" j0={j:>2} closed form {want:>4} waits {ws}") if ws != [want]: bad.append(j) check(f"P2 R = {set(R)}: every sweep answer is the family's rule", ans_off == 0, f"{ans_off} off of {len(cells)}") check(f"P2 R = {set(R)}: at every j0 the waits are exactly " f"2|R| + 2 + j0 (c + 3)", bad == [], f"j0 off: {bad}") w1 = 2 * len(R) + 2 + (c + 3) print(" P4 the plain reader's counted(B, 2) wait at the cells' B: " + ", ".join(f"B={B} {counted(B, 2)[0]}" for B in Bs) + f"; the R-reader at j0 = 1: {w1}") return ans_off, bad def section_plants(R): section(f"B plants at R = {set(R)}") out = {} for pl, what in (("a", "b_2 frozen at False"), ("b", "the D_r tests ignored by the answer")): off, _, _, _, first, _ = p1(R, pl) print(f" ({pl}) {what}: {off} answers off, first {first}") check(f"B{pl} R = {set(R)}: the plant breaks P1", off > 0, f"{off} off") out[pl] = off return out def main(): section_controls() if not all(CHECKS): print("\ncontrols fail: no verdict") return 1 fired = False for R in RS: off, miss = section_answers(R) ans_off, bad = section_sweep(R) pl = section_plants(R) fired |= (off > 0 or miss > 0 or ans_off > 0 or bad != [] or pl["a"] == 0 or pl["b"] == 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())