supplyfloor.py
Checks: SUPPLY: The element machine reads coprimality in 3M + 5B + 3 unit ops with multiply and O(B(B + M)) without theorem.
Cited on: SUPPLY.
To run it: save supplyfloor.py, with coprime.py, coprime_mul.py, supply.py beside it; standard library only.
r"""supplyfloor.py -- without multiply, the path lemma behind a floor of
the order of sqrt(M): the run on p follows the M-free path G until a
tested newest integer is a multiple of p.
QUESTION. The element machine without multiply (coprime.py) reads
whether the newest modulus M is coprime to the deep moduli, B their
largest. Its proved floor, 2 + ceil(log2 M), does not see B. Is there a
floor that grows with B? (ANSWERED BELOW AS: a floor of order sqrt(M),
not of B; see READING.)
THE ARGUMENT (written before the engine).
THE FAMILY. X >= 8, P the primes in (X/2, X], D a nonempty subset of
P. Supply: the moduli of D, then M = p in P, then a fixed tail. The
answer is [p not in D]; B = max D.
(1) Every op is one integer map at every window. A register's NEWEST
INTEGER x is its value on a window over Z born at the grow, the
named register 1 and the rest 0; the p-window holds x mod p.
After v adds or subs every |x| <= 2^v.
(2) A test of r is true iff A and [p | x_r], A the conjunct over the
other windows, a function of the path alone. G is the path that
reads [x_r = 0] for the newest conjunct (the run on a modulus
above every newest integer). On (D, p) the run follows G through
every test before the first test of G with x_r != 0 and p | x_r;
a departure comes there or later.
(3) W* the largest wait over p in P; H the p in P dividing a nonzero
newest integer tested on G within its first W* ops. Every p
outside H runs as G through its answer, so all get G's answer,
and H contains D or P \ D.
(4) With Q tests and V adds or subs, Q + V <= W* - 1, a tested x
after v value ops holds at most v / log2(X/2) primes of P, so
min(|D|, |P \ D|) <= |H| <= sum_j v_j / log2(X/2)
<= (W* - 1)^2 / (4 log2(X/2)),
W* >= 1 + 2 sqrt(log2(X/2) min(|D|, |P \ D|)), at |D| =
ceil(|P|/2) asymptotically sqrt(X / ln 2) ~ 1.2 sqrt(X).
The argument never reads the deep side.
(5) SCOPE (by hand, not run). A cofactor s coprime to P, M = ps,
makes a hit need ps | x and the floor 1 + log2 s + 2 sqrt(...).
A floor in B alone is false: for a finite set R of primes the
upkeep can carry [r | C'] for r in R in the finite control, and a
reader that first tests whether M is an R-number answers those
M in O(M) whatever B is: r | M read while M is measured, a mod-r
counter in the finite control, O(M); M an R-number iff L^j F
tests zero at some j <= log2 M, L the product of R, O(L log M).
At R = {2} the upkeep alone keeps [C' even] (M's parity read
while it measures M), and doubling F in lockstep with a count to
M answers every M = 2^t in O(log M).
(6) THE GAP. The prefix reader shows the family alone allows about
2 |D| log2 X ~ X / (2 ln 2): one new prime of P per test. The
floor is the count of primes of P that tested values can carry;
whether a +/- program of length V can test values carrying many
more than V / log2 X new primes of P is the open question, the
additive face of the wait's reduction to ultimate complexity (a
covering chain plus one multiply per test bounds tau' of the
product of P).
READING (after the run). The floor is not in B. The reduction's
supply, one deep modulus 2 and M <= 2N, already forces G to
hit every odd prime up to N (the runs on p and 2p differ); with (1) and
the step log2 |x_j| <= v_j, sum_j v_j >= log2 of their product,
(theta(N) - ln 2) / ln 2, so the largest wait there is at least
1 + 2 sqrt((theta(N) - ln 2) / ln 2), asymptotically 2 sqrt(N / ln 2):
a largest wait over M <= 2N of order sqrt(M), B = 2, though M = 2^t
alone is answered in O(log M) (see (5)). The family above is that
argument with the deep side made large; it adds no B content, and
the question whether a reader must touch every d <= B stands. What this script checks is the
path lemma (2)-(3) on two readers.
THE REDUCTION SUPPLY (section R; frozen before its code).
Does coprime.py's Reader meet every step of that proof? GROW sets its
register to 1 on the new window and 0 on the others, so F, W = F and
V = jF are 0 on the deep window, and the d = 1 unit loop tests V at
newest integer j, deep zero. G never zeroes V, so it stays in that
loop: its j-th test is at op 7 + 3j from the grow, after v_j = 2j + 1
value ops. The wait is 6M + 29 at odd M and 4.5M + 22 at even M, so
T = 12N + 23 (M = 2N - 1), Q = 4N + 5 tests within it.
PREDICTIONS, N in {11, 23, 47, 97}.
Q1 every answer is [M odd], M = 2 .. 2N; T = 12N + 23.
Q2 each odd prime p <= N first hits G (deep zero, p | x != 0) at the
p-th test, of V, x = p; the run on p departs there, the run on 2p
at the (2p)-th.
Q3 log2(N#/2) <= log2 prod |x_j| = log2(Q!) <= sum v_j = Q^2 + 2Q
<= QV <= (T - 1)^2 / 4 = (6N + 11)^2.
Q4 T above the bound: 155/7.4, 299/11.3, 587/16.2, 1187/22.9.
Control C1 first; plants (a) G run at the real modulus 3, (b) hits
read at p + 2, each must break Q2 at some N. KILL: a prime without a
hit within T, a departure before h_p, a failed link, T <= the bound,
or a plant that breaks nothing.
TWO READERS. coprime.py's Reader, correct on every supply; and the
PREFIX READER for a known D, correct on its family only: X := F, then
for q in D (ascending) X := qX by double-and-add into R, test X; the
first true test answers "not coprime", none answers "coprime".
PREDICTIONS (frozen before this file), X in {16, 24, 32, 48,
64, 96}, D the upper and the lower ceil(|P|/2) primes of P.
P1 both readers answer [p not in D] at every (X, D, p).
P2 the path lemma: the trace (register, outcome) on p departs from
G's at or after h_p, the first G test with p | x != 0; every p
outside H answers as G does through its whole trace.
P3 H contains D for both readers.
P4 |H| < sum_j v_j / log2(X/2), and W* > the floor of (4).
P5 (a print) the prefix reader's W* / floor grows with X like
sqrt(X); W* ~ 2 |D| log2 X.
CONTROLS.
C1 coprime_mul.py's Reader (the multiply reader, whose own run prints
the fact; the freeze named coprime.py's, a slip: the fact is the
multiply reader's) on the deep modulus 2: for odd primes p <= 47
the run on p departs from G at test p, of S, newest integer p.
C2 the prefix reader: h_p for p in D is the test of the first prefix
product holding p.
PLANTS, each must break P2 or P3: (a) G run at a modulus of P \ D, a
real run, not the M-free path; (b) hits read as divisibility by p + 2.
The freeze's plant (a) was G at modulus 257; it was replaced with the
code, unrecorded until a later reading, where a run of it broke 0 of 24:
in 13 runs (the 12 prefix runs and one coprime run) G at 257 tests no
multiple of 257 within W*, so it is G itself, and in the other 11 every
p <= 96 departs before 257 matters.
KILL (frozen). OFF, the count of (X, D, p, reader) violating P2; fires
if OFF > 0, or any W* <= the floor, or P3 fails unplanted.
FINDINGS (entered after the run, from its printed output).
C1 the run on p departs from G at test p, of S = p, at the 14 odd
primes 3 .. 47. C2 h_q is the test of q's prefix product, 0 off.
P1 every answer is [p not in D], 24 (X, D, reader) runs, 0 off.
P2 OFF = 0. P3 H contains D at every run; the coprime reader's H is
all of P (its unit test's V counts through every k on G).
P4 |H| below the cover sum at every run; W* above the floor at
every run: at X = 96, upper D, the coprime reader 35962 and the
prefix reader 72 against 10.5.
P5 its first clause MISSES: the prefix reader's W* / floor (upper
D) reads 2.69, 3.93, 5.86, 4.87, 6.52, 6.89 at X = 16 .. 96, not
monotone. Its second holds within 1.5: W* against 2 |D| log2 X
reads 12/8.0, 25/18.3, 39/30.0, 41/33.5, 57/48.0, 72/65.8. Toy
scale: |P| is 2 to 9.
B plant (a) breaks 11 of 24 runs (the prefix reader's run on a
prime outside D is G itself, so it cannot break there), plant (b)
24 of 24.
K KILL MISSES: OFF = 0, no W* at or below the floor.
R Q1 .. Q4 hold at every N: T = 155, 299, 587, 1187 against the
bound 7.38, 11.34, 16.24, 22.89; every odd prime p <= N hits at
test p, of V, x = p, and the runs on p and 2p depart at tests p
and 2p. At N = 97 the chain reads 119.8 <= 2825.7 <= 155235 <=
309291 <= 351649.0. V is read as the last test's count, 2Q + 1,
not the 2Q + 2 ops within T: the link sum v_j <= Q max v_j holds
the same. Plants (a) and (b) break Q2 at 4 of 4 N. The reader is
linear in M, so the chain is slack by a factor near 3000 at N =
97: this checks the proof's steps, not the floor's order.
KILL MISSES.
RUN RECORD. 27 checks, 6.3 s, 27.8 MB under a memory guard.
"""
import sys
from math import ceil, log, log2, sqrt
from supply import PRIMES, check, section, CHECKS
import coprime
import coprime_mul
from coprime_mul import Mul
BIG = 2 ** 521 - 1 # a prime above every newest integer met
XS = (16, 24, 32, 48, 64, 96)
class Stop(Exception):
pass
class Shadow(Mul):
"""Mul with the newest integers, each test logged as (register,
newest integer, outcome, op index from the grow, value ops before
it); after the grow numbered `final` the run stops past `limit` ops."""
def __init__(self, supply, final, limit=None):
super().__init__(supply, shadow=True)
self.final, self.limit = final, limit
self.t0 = self.vops = None
def tick(self):
if self.t0 is not None and self.limit is not None \
and self.units - self.t0 > self.limit:
raise Stop
def grow(self, into):
super().grow(into)
if len(self.m) - 1 == self.final:
self.t0, self.vops = self.units - 1, 0
self.tick()
def op(self, d, a, b, sign):
super().op(d, a, b, sign)
if self.vops is not None:
self.vops += 1
self.tick()
def mul(self, d, a, b):
super().mul(d, a, b)
if self.vops is not None:
self.vops += 1
self.tick()
def copy(self, d, a):
super().copy(d, a)
self.tick()
def clear(self, d):
super().clear(d)
self.tick()
def zero(self, r):
ans = super().zero(r)
if self.t0 is not None:
r_, x, a = self.tests[-1]
deep0 = set(self.reg(r)) <= {len(self.m) - 1}
self.tests[-1] = (r_, x, a, self.units - self.t0, self.vops,
deep0)
self.tick()
return ans
def run_coprime(ms, limit=None, mul=False):
"""coprime.py's Reader (or coprime_mul.py's) on ms, the last the
newest; returns (answer, wait, tests of the last trip to its read)."""
sup = (lambda i: ms[i] if i < len(ms) else 2)
R = (coprime_mul.Reader if mul else coprime.Reader)(sup)
R.E = Shadow(sup, len(ms) - 1, limit)
try:
for _ in ms:
ans, wait, _ = R.trip()
except Stop:
return None, None, R.E.tests
return ans, wait, [t for t in R.E.tests if t[3] <= wait]
def run_prefix(D, ms, limit=None):
"""The prefix reader for D on ms: deep grows, then the products."""
sup = (lambda i: ms[i] if i < len(ms) else 2)
E = Shadow(sup, len(ms) - 1, limit)
try:
for _ in ms:
E.grow("F")
E.copy("X", "F")
ans = True
for q in sorted(D):
E.clear("R")
for bit in bin(q)[2:]:
E.add("R", "R", "R")
if bit == "1":
E.add("R", "R", "X")
E.copy("X", "R")
if E.zero("X"):
ans = False
break
except Stop:
return None, None, E.tests
return ans, E.units - E.t0, E.tests
def family(X):
P = [p for p in PRIMES if X / 2 < p <= X]
h = ceil(len(P) / 2)
return P, {"upper": P[-h:], "lower": P[:h]}
def floor_of(X, P, D):
return 1 + 2 * sqrt(log2(X / 2) * min(len(D), len(P) - len(D)))
def hit(tests, p, plant=None):
q = p + 2 if plant == "b" else p
return next((j for j, t in enumerate(tests) if t[1] and t[1] % q == 0),
None)
def depart(a, b):
return next((j for j, (s, t) in enumerate(zip(a, b))
if (s[0], s[2]) != (t[0], t[2])), None)
def study(X, P, D, reader, plant=None):
"""One (X, D, reader): P1 .. P4's numbers, the path lemma's OFF."""
ms = sorted(D)
go = (lambda M, lim=None: run_prefix(D, ms + [M], lim)) \
if reader == "prefix" else \
(lambda M, lim=None: run_coprime(ms + [M], lim))
runs = {p: go(p) for p in P}
wrong = sum(runs[p][0] != (p not in D) for p in P)
wstar = max(r[1] for r in runs.values())
gmod = min(set(P) - set(D)) if plant == "a" else BIG
_, _, G = go(gmod, wstar)
G = [t for t in G if t[3] <= wstar]
assert all(abs(t[1]) < BIG // 2 for t in G)
H = {p for p in P if any(t[1] and t[1] % p == 0 for t in G)}
off = 0
for p in P:
tr = runs[p][2]
h = hit(G, p, plant)
d = depart(tr, G)
if d is not None and (h is None or d < h):
off += 1
elif p not in H and d is not None:
off += 1
cover = sum(t[4] for t in G if t[1]) / log2(X / 2)
return dict(wrong=wrong, wstar=wstar, H=H, off=off, cover=cover,
floor=floor_of(X, P, D), tests=len(G))
def section_control():
section("C controls: the M-free path at known departures")
rows, bad = [], 0
for p in [q for q in PRIMES if 2 < q <= 47]:
ans, wait, tr = run_coprime([2, p], mul=True)
_, _, G = run_coprime([2, BIG], wait, mul=True)
h, d = hit(G, p), depart(tr, G)
ok = h == d == p - 1 and G[h][0] == "S" and G[h][1] == p
bad += not ok
rows.append(f"{p}:{d + 1}")
print(" C1 multiply reader, deep 2: p:departure test " + " ".join(rows))
check("C1 the run on p departs from G at test p, of S = p", bad == 0,
f"{bad} off")
bad = 0
for X in XS:
P, Ts = family(X)
for name, D in Ts.items():
ms = sorted(D)
_, _, G = run_prefix(D, ms + [BIG])
for i, q in enumerate(ms):
bad += hit(G, q) != i
check("C2 prefix reader: h_q is the test of q's prefix product",
bad == 0, f"{bad} off")
def section_family():
section("F the family: answers, the path lemma, the cover, the floor")
print(f" {'X':>3} {'D':>5} {'reader':>7} {'|P|':>3} {'|D|':>3} "
f"{'W*':>6} {'floor':>6} {'|H|':>3} {'cover<':>8} "
f"{'tests':>5} {'off':>3}")
OFF = wrong = low = nocov = loose = 0
pre = []
for X in XS:
P, Ts = family(X)
for name, D in Ts.items():
for reader in ("coprime", "prefix"):
s = study(X, P, D, reader)
OFF += s["off"]
wrong += s["wrong"]
low += s["wstar"] <= s["floor"]
nocov += not set(D) <= s["H"]
loose += not len(s["H"]) < s["cover"]
print(f" {X:>3} {name:>5} {reader:>7} {len(P):>3} "
f"{len(D):>3} {s['wstar']:>6} {s['floor']:>6.1f} "
f"{len(s['H']):>3} {s['cover']:>8.1f} "
f"{s['tests']:>5} {s['off']:>3}")
if reader == "prefix":
pre.append((X, s["wstar"], s["floor"],
2 * len(D) * log2(X)))
check("P1 every answer is [p not in D]", wrong == 0, f"{wrong} off")
check("P2 the path lemma: OFF = 0", OFF == 0, f"OFF = {OFF}")
check("P3 H contains D", nocov == 0, f"{nocov} misses")
check("P4 |H| < sum v_j / log2(X/2)", loose == 0, f"{loose} over")
check("P4 W* > the floor", low == 0, f"{low} at or below")
print(" P5 prefix reader: X W* floor W*/floor 2|D|log2 X")
for X, w, f, est in pre:
print(f" {X:>3} {w:>5} {f:>6.1f} {w / f:>6.2f} {est:>8.1f}")
return OFF, low
def section_plants():
section("B plants must break P2 or P3")
for plant, what in (("a", "G at a modulus of P \\ D"),
("b", "hits read at p + 2")):
broke = 0
for X in XS:
P, Ts = family(X)
for D in Ts.values():
for reader in ("coprime", "prefix"):
s = study(X, P, D, reader, plant)
broke += s["off"] > 0 or not set(D) <= s["H"]
check(f"B{plant} {what} breaks a run", broke > 0,
f"{broke} of {2 * 2 * len(XS)} runs broken")
def odd_primes(N):
return [p for p in range(3, N + 1)
if all(p % q for q in range(2, int(p ** 0.5) + 1))]
def bound(N):
theta = sum(log(p) for p in [2] + odd_primes(N))
return 1 + 2 * sqrt((theta - log(2)) / log(2))
def reduction(N, plant=None):
"""coprime.py's Reader on the deep modulus 2, M = 2 .. 2N: Q1 .. Q4's
numbers and the departures that break Q2."""
runs = {M: run_coprime([2, M]) for M in range(2, 2 * N + 1)}
wrong = sum(runs[M][0] != (M % 2 == 1) for M in runs)
T = max(r[1] for r in runs.values())
_, _, G = run_coprime([2, 3 if plant == "a" else BIG], T)
G = [t for t in G if t[3] <= T]
assert all(abs(t[1]) < BIG // 2 for t in G)
off, rows = 0, []
for p in odd_primes(N):
q = p + 2 if plant == "b" else p
h = next((j for j, t in enumerate(G)
if t[5] and t[1] and t[1] % q == 0), None)
d1, d2 = depart(runs[p][2], G), depart(runs[2 * p][2], G)
bad = h is None or (d1 is not None and d1 < h) \
or (d2 is not None and d2 < h) or (d1 is None and d2 is None)
off += bad
rows.append((p, h, d1, d2, G[h][0] if h is not None else "-",
G[h][1] if h is not None else 0))
Q = len(G)
V = max(t[4] for t in G)
vals = [abs(t[1]) for t in G if t[1]]
prim = sum(log2(p) for p in odd_primes(N))
chain = (prim, sum(log2(x) for x in vals), sum(t[4] for t in G if t[1]),
Q * V, (T - 1) ** 2 / 4)
return dict(wrong=wrong, T=T, Q=Q, V=V, off=off, rows=rows,
chain=chain, bound=bound(N))
NS = (11, 23, 47, 97)
def section_reduction():
section("R the reduction supply: deep 2, M <= 2N, the sqrt(M) floor")
fired = 0
for N in NS:
r = reduction(N)
print(f" N = {N}: T = {r['T']} (12N + 23 = {12 * N + 23}), "
f"Q = {r['Q']} (4N + 5 = {4 * N + 5}), V = {r['V']}, "
f"bound {r['bound']:.2f}, wrong {r['wrong']}, off {r['off']}")
print(" p:h/d(p)/d(2p) " + " ".join(
f"{p}:{h + 1}/{a + 1}/{b + 1}{g}={x}" if None not in (h, a, b)
else f"{p}:{h}/{a}/{b}" for p, h, a, b, g, x in r["rows"]))
c = r["chain"]
print(" chain: log2(N#/2) {:.1f} <= log2 prod|x| {:.1f} <= "
"sum v {} <= QV {} <= (T-1)^2/4 {:.1f}".format(*c))
links = all(c[i] <= c[i + 1] + 1e-9 for i in range(4))
q2 = all(h == p - 1 and a == p - 1 and b == 2 * p - 1 and x == p
for p, h, a, b, g, x in r["rows"])
check(f"Q1 N = {N}: every answer [M odd], T = 12N + 23",
r["wrong"] == 0 and r["T"] == 12 * N + 23)
check(f"Q2 N = {N}: h_p = test p, x = p; departures p and 2p",
q2 and r["off"] == 0, f"off {r['off']}")
check(f"Q3 N = {N}: every link of the chain holds", links)
check(f"Q4 N = {N}: T above the bound", r["T"] > r["bound"])
fired += r["off"] > 0 or not links or r["T"] <= r["bound"]
broke = {}
for plant in ("a", "b"):
broke[plant] = sum(reduction(N, plant)["off"] > 0 for N in NS)
check(f"R{plant} plant breaks Q2 at some N", broke[plant] > 0,
f"{broke[plant]} of {len(NS)} N")
return fired + sum(v == 0 for v in broke.values())
def main():
section_control()
OFF, low = section_family()
section_plants()
fired_r = section_reduction()
section("K the kill")
print(f" the reduction section's kill {'FIRES' if fired_r else 'MISSES'}")
fired = OFF > 0 or low > 0 or not all(CHECKS)
print(f" OFF = {OFF}, W* at or below the floor at {low} runs")
print(f" KILL {'FIRES' if fired else 'MISSES'}")
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass")
return 0 if all(CHECKS) else 1
if __name__ == "__main__":
sys.exit(main())