rreader.py
Checks: SUPPLY: A fresh trip waits at least log₂(C′/s) to read coprimality theorem.
Cited on: SUPPLY.
To run it: save rreader.py, with coprime.py, supply.py beside it; standard library only.
"""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())