track.py
Checks: IMAGE: Polynomial slack reaches breadth from the void theorem; rule.
Cited on: IMAGE.
To run it: save track.py, with bridges.py, cgreedy.py, growth.py beside it; standard library only.
"""track.py -- does a run escape under the least slack the dam allows?
QUESTION. The dam: if f(tau(P)) < P+, every f-greedy run from a seed on
the primes <= P is dammed. F(t) = max{P+ : tau(P) <= t} (t >= 4, and
F(3) = 5) is, on t >= 4, the least nondecreasing slack meeting f(tau(P)) >= P+ at
every P. Does some F-greedy run from the void escape?
DESIGN. A run crossing from max prime P takes a move holding a prime
R > P, so F(m0) >= R and m0 >= tau(P): with f = F a run crosses only
from a state whose tide is the largest any state on its primes holds.
A PLAIN run seats one odd prime per move, never 2, every exponent 1: a
subclass of the F-greedy runs, so a plain witness is a witness. Its
state is a set S of odd primes, lambda's valuations vN, and the tide by
the door formulas: 2 prices 2^(v+3); a seated q prices q^(v+1); an
unseated q prices q when q - 1 does not divide lambda, else q^(v+2);
v = v_q(lambda) (the void's tide is 3).
(1) THE GREEDY RUN seats the lambda-raising odd prime p <= F(m0) whose
seat gives the largest tide, ties to the larger p, until no move is
left (dammed at its max prime) or F(m0) passes the table (through).
(2) THE PLAIN SEARCH visits every set reachable by plain moves whose
primes stay <= PCAP and reports whether any move passes PCAP.
(3) THE CAPPED WALK does the same over the full walk, every composite
move m <= F(m0), exponents capped (3 at odd primes, 5 at 2), its m0 by
growth.menu.
(4) THE ANCHOR. A state holding an odd prime q and no prime = 1 mod q
has v_q(lambda) = q's own part, so the move q raises lambda and
m0 <= q. If f(q) < p(q), p(q) the least prime = 1 mod q, every later
move is <= f(q) < p(q) and q stays unanchored: the run's primes stay
<= max(the state's, f(q)). The same holds at depth: q held at exactly
exponent a with no held prime = 1 mod q^a has v_q(lambda) = a - 1, so
m0 <= q, and f(q) < p(q^a) dams (the seeds 3^N are q = 3, a = N). So
in an escaping run every such (q, a) at every state has
f(q) >= p(q^a), every RECORD prime among them (the largest prime of
the support right after the move that brings it in, unanchored at
entry). The run holds an infinite ANCHOR CHAIN q_0 < q_1 < ...,
q_(i+1) = 1 mod q_i, q_(i+1) <= f(q_i): q_0 a record prime past the
seed, q_(i+1) the first prime = 1 mod q_i to enter, which exists (else
q_i stays unanchored, m0 <= q_i forever and the support stays below
f(q_i)); at its move the least j with q_(j+1) unheld has q_j held (q_0
by recordness, q_j for j >= 1 since j - 1 is not least) and unanchored
(q_(j+1) is the first prime = 1 mod q_j ever to enter), so
m0 <= q_j <= q_i and q_(i+1) <= m <= f(q_i).
f < L(t) = min{p(q) : q prime >= t} past some t is dammed from
every seed (a record prime past t enters unanchored);
f >= U(t) = max{p(s) : s prime power <= t} is where the record run
escapes. Where L(t) <= ct the class f < L lies
inside the linear slacks the covering dams; the anchor's own force is
per run.
PREDICTIONS (frozen before the code).
T1 (forced) void -> 5 -> 55 -> 715 holds tides 5, 7, 11; 5 -> 35 -> 385
has tide 7 and no plain move left.
T2 (a guess, 40%) the greedy run passes P = 1000.
T3 (a guess, 70%) the plain search passes PCAP = 100.
A1 (forced) m0 <= q at every unanchored odd q of every state visited.
A2 (forced) under f = L - 1, from the void, 3, 5, 7 and 3*5*7 (PCAP
60), no move passes f(q) or brings a prime = 1 mod q, q unanchored.
A3 (a reading) L(t)/t in [2, 3] at most t <= 10^4; U(t)/t past 10.
KILL. "T KILL" printed if the plain search and the capped walk both find
every run dammed below their PCAP; a plain dam alone prints "plain dam".
CONTROLS, read first. C1 the engine's tide equals cgreedy.m0 on every
state of the hand paths and of the greedy path; C2 F(5) = 11, F(7) = 13,
F(11) >= 17; C3 the path checker flags a planted move 1 past F(m0) and
a planted non-raising move; C4 L(t) needs no q past the prime list;
C5 A2's test flags the record run's path under f = L - 1. A2 cannot
fail apart from A1: the walk tries only m <= f(m0), so m > f(q) needs
m0 > q, and a prime = 1 mod q needs m >= p(q) > f(q). Changed from
the frozen form: A2 was frozen as a bound on held primes and is run
per edge (the bound follows by induction);
the frozen control, f = U on the record path, could not fire through a
test gated on f(q) < p(q), so C5 plants the record path under L - 1;
A1's frozen scope over the plain search's sets was not run.
FINDINGS (from the printed run; the controls passed first, F(11) = 23).
T1 held. T2 and T3 failed: the greedy run is dammed after 6 seats,
5, 11, 13, 23, 19, 17, at max prime 23 with tide 13 where tau(23) = 17;
the plain search reaches 15 sets, every one on the primes <= 23; the
capped walk reaches 591 states at PCAP 30 and 40, top prime 23. KILL:
"T KILL", F does not suffice from the void. The reason, by hand and
uncapped: a run past 11 holds 13 (F(tau(11)) = 13 is the only way on),
13 prices 13 until a prime = 1 mod 13 is held, the least 53, and every
move is <= F(13) = 23: every F-greedy run from the void stays on the
primes <= 23. A1 holds at all 687 states, the union of the F walk's
(PCAP 40) and the L - 1 walks', A2 at every edge; the L - 1 walks reach 129, 26,
44, 36 and 39 states, top prime 7, none past 60; C5 flags the record
run at its move 7 (q = 3, L(3) - 1 = 6). A3: L(t)/t in [2, 3] at 9990
of the 9999 t in 2..10^4 (1.500 at t = 2, max 3.917); U(t)/t reaches
76.00 at t = 5227 (p(5227) = 397253); L(10^4) = 20123, U(10^4) = 496747.
RUN RECORD. PCAPS=30 WCAPS=20: 6/6, 0.0 s, peak commit 38.2 MB.
PCAPS=30 WCAPS=30,40: 6/6, 0.1 s, peak commit 38.1 MB. With the
anchor, PCAPS=30 WCAPS=30: 10/10, 0.1 s, peak commit 40.4 MB. p_of
corrected at even q (it gave p(4) = 17, not 5), PCAPS=30 WCAPS=30,40:
10/10, 0.5 s, peak commit 40.6 MB, every print unchanged.
"""
import os
import time
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import growth # noqa: E402
import cgreedy # noqa: E402
CHECKS = []
ODD = [p for p in cgreedy.PR if p > 2]
PM1 = cgreedy.PM1
TAB = cgreedy.tau_table()
TP = sorted(TAB) # the primes <= X
PTOP = TP[-1]
def check(name, ok, detail=""):
CHECKS.append((name, bool(ok)))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def F(t):
"""The least escaping slack, or None past the table."""
if t < 4:
return 5
last = None
for P in TP:
if TAB[P][0] <= t:
last = P
else:
break
if last is None or last == PTOP:
return None
return cgreedy.next_prime(last)
def add_v(vN, p):
out = dict(vN)
for r, e in PM1[p].items():
if e > out.get(r, 0):
out[r] = e
return out
def tide(S, vN):
if not S:
return 3
best = 2 ** (vN.get(2, 0) + 3)
for q in ODD:
if q >= best:
break
if q in S:
pr = q ** (vN.get(q, 0) + 1)
elif not growth.divides(PM1[q], vN):
pr = q
else:
pr = q ** (vN.get(q, 0) + 2)
if pr < best:
best = pr
return best
def moves(S, vN, m):
f = F(m)
if f is None:
return None
return [p for p in ODD if p <= f and p not in S
and not growth.divides(PM1[p], vN)]
def legal(path):
"""Replay a plain path: every move raises lambda and is <= F(m0)."""
S, vN = set(), {}
for p in path:
f = F(tide(S, vN))
if f is None or p > f or p in S or growth.divides(PM1[p], vN):
return False
S.add(p)
vN = add_v(vN, p)
return True
def state_of(path):
S, vN = set(), {}
for p in path:
S.add(p)
vN = add_v(vN, p)
return S, vN
def menu_tide(S):
return cgreedy.m0({p: 1 for p in S}) if S else 3
def greedy_run():
S, vN, path = set(), {}, []
while True:
m = tide(S, vN)
cand = moves(S, vN, m)
if cand is None:
return path, m, "through"
if not cand:
return path, m, "dammed"
best = None
for p in cand:
t = tide(S | {p}, add_v(vN, p))
if best is None or (t, p) > best:
best = (t, p)
p = best[1]
S.add(p)
vN = add_v(vN, p)
path.append(p)
def plain_search(pcap, budget=2_000_000):
seen = {frozenset()}
stack = [frozenset()]
top = 0
while stack:
S = stack.pop()
vN = {}
for p in S:
vN = add_v(vN, p)
cand = moves(S, vN, tide(S, vN))
if cand is None:
return True, len(seen), top
for p in cand:
if p > pcap:
return True, len(seen), top
T = S | {p}
if T not in seen:
seen.add(T)
top = max(top, p)
stack.append(T)
if len(seen) > budget:
return None, len(seen), top
return False, len(seen), top
CAP2, CAPO = 5, 3
def capped_walk(pcap, budget=300_000):
start = ()
seen = {start}
stack = [start]
top = 0
while stack:
st = stack.pop()
mf = dict(st)
lf = cgreedy.lam(mf)
m0 = cgreedy.m0(mf) if mf else 3
f = F(m0)
if f is None:
return True, len(seen), top
for m in range(2, f + 1):
fm = growth.factor(m)
nf = growth.merge_add(mf, fm)
if cgreedy.lam(nf) == lf:
continue
if max(nf) > pcap:
return True, len(seen), top
if any(e > (CAP2 if q == 2 else CAPO) for q, e in nf.items()):
continue
key = tuple(sorted(nf.items()))
if key not in seen:
seen.add(key)
top = max(top, max(nf))
stack.append(key)
if len(seen) > budget:
return None, len(seen), top
return False, len(seen), top
# ---------------------------------------------------------------- anchor
def p_of(q):
"""The least prime = 1 mod q, q >= 2 (k even at odd q, any k at
even q)."""
step = 2 if q % 2 else 1
k = step
while not growth.is_prime(k * q + 1):
k += step
return k * q + 1
PQ = {}
def pq(q):
if q not in PQ:
PQ[q] = p_of(q)
return PQ[q]
TL = 10_000
QL = [q for q in growth.PRIMES if q <= 2 * TL + 2000]
def l_table():
"""L(t) = min p(q) over primes q >= t, for 1 <= t <= TL, checked to
need no q past the list (p(q) >= 2q + 1 at odd q)."""
out, run, j = {}, None, len(QL) - 1
ok = True
for t in range(TL, 0, -1):
while j >= 0 and QL[j] >= t:
v = pq(QL[j])
run = v if run is None or v < run else run
j -= 1
out[t] = run
ok = ok and 2 * QL[-1] + 1 >= run
return out, ok
def u_table():
"""U(t) = max p(s) over prime powers s <= t, for 1 <= t <= TL."""
pps = set()
for p in growth.PRIMES:
if p > TL:
break
x = p
while x <= TL:
pps.add(x)
x *= p
out, run = {}, 0
for t in range(1, TL + 1):
if t in pps:
run = max(run, p_of(t) if t not in PQ else PQ[t])
out[t] = run
return out
def unanchored(mf):
held = [p for p in mf if p > 2]
return [q for q in held if not any((p - 1) % q == 0 for p in held)]
def walk(f, start, pcap, budget=300_000, edge=None):
"""Every state the capped walk under f reaches from start; edge(mf,
m, nf) is called on every move taken."""
key0 = tuple(sorted(start.items()))
seen, stack = {key0}, [key0]
passed = False
while stack:
mf = dict(stack.pop())
lf = cgreedy.lam(mf)
m0 = cgreedy.m0(mf) if mf else 3
for m in range(2, f(m0) + 1):
nf = growth.merge_add(mf, growth.factor(m))
if cgreedy.lam(nf) == lf:
continue
if edge:
edge(mf, m, nf)
if max(nf) > pcap:
passed = True
continue
if any(e > (CAP2 if q == 2 else CAPO) for q, e in nf.items()):
continue
key = tuple(sorted(nf.items()))
if key not in seen:
seen.add(key)
stack.append(key)
if len(seen) > budget:
return seen, None
return seen, passed
def a1_bad(states):
bad = []
for key in states:
mf = dict(key)
if not mf:
continue
m = cgreedy.m0(mf)
bad += [(key, q) for q in unanchored(mf) if m > q]
return bad
def a2_edge(f, bad):
def edge(mf, m, nf):
for q in unanchored(mf):
if f(q) < pq(q) and (m > f(q) or any(
(p - 1) % q == 0 for p in nf if p > 2 and p not in mf)):
bad.append((tuple(sorted(mf.items())), m, q))
return edge
def section_anchor():
print("THE ANCHOR DAM")
t0 = time.time()
L, lok = l_table()
U = u_table()
check("C4 L(t) needs no prime past the list at t <= 10,000", lok)
fL = lambda t: L[min(t, TL)] - 1 # noqa: E731
walks = {}
bad2 = []
for name, seed in (("void", {}), ("3", {3: 1}), ("5", {5: 1}),
("7", {7: 1}), ("3*5*7", {3: 1, 5: 1, 7: 1})):
st, passed = walk(fL, seed, 60, edge=a2_edge(fL, bad2))
walks[name] = (st, passed)
top = max((max(dict(k)) for k in st if k), default=0)
print(f" f = L - 1 from {name:5s}: {len(st)} states, top prime "
f"{top}, passes 60: {passed}")
stF, _ = walk(lambda t: F(t) if F(t) else t, {}, 40)
states = set(stF)
for st, _ in walks.values():
states |= st
b1 = a1_bad(states)
for key, q in b1[:3]:
print(f" A FAIL A1 at {key}, q = {q}")
for key, m, q in bad2[:3]:
print(f" A FAIL A2 at {key}, move {m}, q = {q}")
check(f"A1 m0 <= q at every unanchored odd q, {len(states)} states",
not b1)
check("A2 under f = L - 1 no move passes f(q) or brings a prime = 1"
" mod q, q unanchored", not bad2, f"{len(bad2)} edges")
rec, S, vN = [], set(), {}
for p in ODD:
if p > 200:
break
if not growth.divides(PM1[p], vN):
rec.append(p)
S.add(p)
vN = add_v(vN, p)
plant, mf = [], {}
edge = a2_edge(fL, plant)
for p in rec:
nf = growth.merge_add(mf, {p: 1})
edge(mf, p, nf)
mf = nf
check("C5 A2's test flags the record run's path under f = L - 1",
len(plant) > 0, f"first at move {plant[0][1] if plant else None}"
f", q = {plant[0][2] if plant else None}")
rl = [L[t] / t for t in range(2, TL + 1)]
ru = [U[t] / t for t in range(2, TL + 1)]
inb = sum(2 <= r <= 3 for r in rl)
top_u = max(range(2, TL + 1), key=lambda t: U[t] / t)
print(f" A3 reading: L(t)/t in [2, 3] at {inb} of {len(rl)} t, max "
f"{max(rl):.3f}, min {min(rl):.3f}; U(t)/t max {max(ru):.2f} at "
f"t = {top_u} (U = {U[top_u]}); at t = 10,000 L = {L[TL]}, "
f"U = {U[TL]} ({time.time() - t0:.1f} s)")
def section_controls():
print("CONTROLS")
hand = [[5], [5, 11], [5, 11, 13], [5, 7], [5, 7, 11]]
bad = [h for h in hand
if tide(*state_of(h)) != menu_tide(state_of(h)[0])]
check("C1 the tide equals cgreedy.m0 on the hand paths", not bad,
f"{len(bad)} differ")
check("C2 F(5) = 11, F(7) = 13, F(11) >= 17",
F(5) == 11 and F(7) == 13 and F(11) >= 17,
f"F(5) = {F(5)}, F(7) = {F(7)}, F(11) = {F(11)}")
check("C3 the checker flags 17 past F(m0) = 13 at 5, 11 and a"
" non-raising 13 at 5, 7, 11",
legal([5, 11, 13]) and not legal([5, 11, 17])
and not legal([5, 7, 11, 13]))
def section_hand():
print("T1 THE HAND STEPS")
tides = [tide(*state_of(h)) for h in ([5], [5, 11], [5, 11, 13])]
S, vN = state_of([5, 7, 11])
left = moves(S, vN, tide(S, vN))
check("T1 void -> 5 -> 55 -> 715 at tides 5, 7, 11; 5 -> 35 -> 385 at"
" tide 7 with no plain move", tides == [5, 7, 11]
and tide(S, vN) == 7 and left == [],
f"tides {tides}, 385: tide {tide(S, vN)}, moves {left}")
def section_greedy():
print("T2 THE GREEDY RUN")
t0 = time.time()
path, m, how = greedy_run()
S, vN = state_of(path)
print(f" {how} after {len(path)} seats, max prime {max(path)}, tide "
f"{m}, tau there {TAB[max(p for p in TP if p <= max(path))][0]}"
f" ({time.time() - t0:.1f} s)")
print(f" first seats: {path[:20]}")
bad, Sx, vx = 0, set(), {}
for p in path[:300]:
Sx.add(p)
vx = add_v(vx, p)
if tide(Sx, vx) != menu_tide(Sx):
bad += 1
check("C1 the tide equals cgreedy.m0 along the greedy path (first 300"
" states)", bad == 0, f"{bad} differ")
check("C3 the greedy path replays legal", legal(path))
return path, how
def main():
t0 = time.time()
section_controls()
if not all(ok for _, ok in CHECKS):
print("CONTROL FAILED: nothing below is read.")
raise SystemExit(1)
section_hand()
path, how = section_greedy()
print("T3 THE SEARCHES")
res = {}
for pcap in (int(a) for a in os.environ.get("PCAPS", "30,60,100")
.split(",")):
t1 = time.time()
ok, n, top = plain_search(pcap)
res[("plain", pcap)] = ok
print(f" plain PCAP {pcap:4d}: passes {ok}, {n} sets, top "
f"{top} ({time.time() - t1:.1f} s)")
for pcap in (int(a) for a in os.environ.get("WCAPS", "30").split(",")):
t1 = time.time()
ok, n, top = capped_walk(pcap)
res[("walk", pcap)] = ok
print(f" capped PCAP {pcap:4d}: passes {ok}, {n} states, top "
f"{top} ({time.time() - t1:.1f} s)")
section_anchor()
print("KILL")
plain_dam = any(v is False for (k, _), v in res.items() if k == "plain")
walk_dam = any(v is False for (k, _), v in res.items() if k == "walk")
print(" " + ("T KILL" if plain_dam and walk_dam else
"plain dam" if plain_dam else "silent"))
print(f"{sum(ok for _, ok in CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(ok for _, ok in CHECKS) else 1)
if __name__ == "__main__":
main()