envelope.py
Checks: IMAGE: Polynomial slack reaches breadth from the void theorem; rule.
Cited on: IMAGE.
To run it: save envelope.py, with bridges.py, cgreedy.py, growth.py, slack.py beside it; standard library only.
"""envelope.py -- where the record run's own slack sits, and what every
run from the void owes at each prime power.
QUESTION. The record run (read the odd primes in order from the void,
seat each p whose p - 1 does not divide lambda) is f-greedy exactly
when f(m0(M)) >= R at each seat state M and the seat R taken from it,
so E(t) = max{R : m0(M) <= t} is the least nondecreasing slack it
escapes under. Where does E sit between min{p(q) : q prime >= t} and
U(t) = max{p(s) : s prime power <= t}, p(s) the least prime = 1 mod s,
at t <= 10^4? What does every run from the void owe pointwise?
DESIGN. u_r is the largest v_r(p - 1) over the held primes p (odd p at
r = 2). The door formulas give the price at an odd prime r: unheld, r
when r - 1 does not divide lambda, else r^(u_r + 2); held at exponent
a, r^max(1, u_r - a + 2). At 2, unheld at odd M, 2^(w + 3), w = u_2 (4
at w = 0), and a seated 2 prices lower. So m0 <= r^(u_r + 2) at every
odd r, m0 <= r^(u_r + 1) at a held r, m0 <= 2^(u_2 + 3).
(1) THE DEPTH DAM. An escaping run's tide is unbounded (a tide at most
T keeps every move at most f(T)), so every u_r is, and for each e past
the seed's u_r one move lifts u_r from at most e - 1 to at least e. It
brings a prime = 1 mod r^e, at least p(r^e), from a tide at most
r^(e + 1) (odd r), r^max(1, e - a + 1) (r held at exponent a, so r^e
at a = 1 and r itself at e <= a), 2^(e + 2) (r = 2). From the void every
escaping run has f(r^(e+1)) >= p(r^e) at every odd r and e >= 1 and
f(2^(e+2)) >= p(2^e) at every e >= 1: one (r, e) failing dams every
run from the void. B(t) is the largest of those p(r^e) whose point
r^(e+1) or 2^(e+2) is at most t. The anchor is its held case at e = a
(tide at most r, so f(r) >= p(r^a)), the seeds 3^N that case at r = 3,
a = N, from a seed, and the covering's 2-adic step its case r = 2.
(2) E <= U. m0(M_P) >= beta(P), and beta(P) <= t iff some prime power
s <= t is unborn at P iff P < U(t); for such P, U(t) = p(s*) with s*
unborn, so U(t) - 1 does not divide lambda and U(t) is seated: R <= U(t).
(3) E = U at t when m0(M*) <= t, M* the state U(t) is seated from; so
whenever s* = r^e has r seated, as m0 <= r^(u_r + 1) <= r^e = s* <= t.
(4) E >= S(t) = max{p(r^e) : r seated, r^e <= t}: a record r enters
with u_r = 0 at exponent 1, so each crossing of e is from a tide at
most r^e. And E >= B by (1), E's run escaping.
(5) E <= max(S, B, t), derived after the first run from its readings.
The tide m0 of a seat state is a price, and the next seat R is at most:
p(s), s = m0 = r^(u_r + 1), at a seated r (s is unborn, so p(s) is
unread and seated, and p(s) <= S(m0)); m0 itself at an unheld r with
r - 1 not dividing lambda (r is then unread, a read one being skipped
only with r - 1 | lambda); p(m0 / r) at an unheld r with r - 1 | lambda,
and p(m0 / 4) at 2 (w >= 1 past the void, whose tide 3 is no price at
2), each an unborn prime power at the point m0 of B.
With (4), E = max(S, B) wherever that is at least t.
The run is read until beta(P) > 10^4, past U(10^4), so every seat state
with m0 <= 10^4 is seen.
PREDICTIONS (frozen before the code).
P1 (forced) E <= U at every t <= 10^4.
P2 (forced) E >= S and E >= B (nondecreasing hulls) at every t.
P3 (forced) E = U at every t whose s* has its prime seated; (a guess,
80%) E = U at >= 90% of t <= 10^4 overall.
P4 (a guess, 60%) B(t)/t <= 5 at every t <= 10^4, and B(t) below
min{p(q) : q >= t} at most t.
KILL. "E KILL" printed if P1 or P2 fails at any t. Readings, not
kills: the share of t with E = U, the largest E/t and B/t, where B and
the least p(q) cross.
CONTROLS, read first. C1 the price formula's m0 equals cgreedy.m0 on
the record run's first 150 seat states. C2 its seats to 10^4 equal
slack.py's. C3 P2's B arm alone flags E set to B - 1 at the t of B's
largest value, B(2048) = p(2^9) = 7681 is checked against a hand
value, and P1's test flags E raised past U at one t. C4 the last state read has
m0 > 10^4. C5, added with (5): P5's test flags E raised by 1 at 5000, read
first.
FINDINGS (from the printed run; the controls passed first). KILL
silent. The record run reads to its seat 496997, 7352 seats, the last
m0 12919. P1, P2 hold at every t in 1..10^4; P3's forced half holds at
its 2640 t, and its guess fails: E = U at those 2640 of the 9999 t in
2..10^4 only, every other t having s* a power of a skipped prime (7358
t) or of 2 (1 t); the least E/U over 3..10^4 is 0.370. P5: E <= max(S,
B, t) at every t in 2..10^4 and E = max(S, B) wherever max(S, B) >= t,
the condition failing at t = 2 alone. B never binds: E = S at all 9999 t, B > S at
none. E/t is largest at 229981/3833 = 60.0003, U/t at 397253/5227 =
76.0002, B/t at 7681/2048 = 3.7505; at t = 10^4, E = S = 359747,
U = 496747, B = 17497. P4: B <= 5t at every t, but B is below
min{p(q) : q >= t} at only 3734 of the 9999 t, the two crossing at
4 t, the last 8742.
RUN RECORD. First run: MemoryError at the 512 MB cap (a held set kept
per seat); kept for the first 150 only: 7/7, 2.4 s, 63.5 MB. With P5 and
C5: 9/9, 2.5 s, peak commit 62.9 MB. An audit: the depth dam's held case
written at exponent a, C5 made to run P5's test before the gate, P5's
equality restricted to max(S, B) >= t and counted, the readings printed
to four places with E = S: 9/9, 2.4 s, 63.0 MB.
"""
import os
import time
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import growth # noqa: E402
import cgreedy # noqa: E402
import slack # noqa: E402
CHECKS = []
T = 10_000
N = 700_000 # past U(10^4) = 496747 and its next seat
def check(name, ok, detail=""):
CHECKS.append((name, bool(ok)))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def spf_sieve(n):
spf = list(range(n + 1))
for i in range(2, int(n ** 0.5) + 1):
if spf[i] == i:
for j in range(i * i, n + 1, i):
if spf[j] == j:
spf[j] = i
return spf
SPF = spf_sieve(N)
PRIMES = [p for p in range(2, N + 1) if SPF[p] == p]
FAC = {}
def fac(n):
if n not in FAC:
out, m = {}, n
while m > 1:
q = SPF[m]
out[q] = out.get(q, 0) + 1
m //= q
FAC[n] = out
return FAC[n]
def divides(fm, vN):
return all(vN.get(r, 0) >= e for r, e in fm.items())
def p_of(s):
"""The least prime = 1 mod s, s >= 2."""
n = s + 1
while True:
if n <= N:
if SPF[n] == n:
return n
elif growth.is_prime(n):
return n
n += s
def m0_of(held, vN):
"""The tide of the odd squarefree state on held, lambda's exponents
vN, by the door formulas."""
w = vN.get(2, 0)
best = 4 if w == 0 else 2 ** (w + 3)
for r in PRIMES[1:]:
if r >= best:
break
u = vN.get(r, 0)
if r in held:
pr = r ** (u + 1)
elif not divides(fac(r - 1), vN):
pr = r
else:
pr = r ** (u + 2)
if pr < best:
best = pr
return best
def record_run():
"""[(m0 of the seat state, the next seat)], from the void, until a
state's m0 passes T; and the seats."""
held, vN, seats = set(), {}, []
pairs = []
m = 3 # the void's tide
for p in PRIMES[1:]:
if divides(fac(p - 1), vN):
continue
pairs.append((m, p, frozenset(held) if len(pairs) < 150 else None))
held.add(p)
seats.append(p)
for r, e in fac(p - 1).items():
if e > vN.get(r, 0):
vN[r] = e
m = m0_of(held, vN)
if m > T and p > 496_747:
return pairs, seats, m, p
return pairs, seats, m, None
def prime_powers(n):
out = []
for r in PRIMES:
if r > n:
break
q, a = r, 1
while q <= n:
out.append((q, r, a))
q, a = q * r, a + 1
return sorted(out)
def hull(points):
"""The nondecreasing step function t -> max{v : point <= t} on
1..T, from [(point, v)]."""
best, out, j = 0, [0] * (T + 1), 0
points = sorted(points)
for t in range(1, T + 1):
while j < len(points) and points[j][0] <= t:
best = max(best, points[j][1])
j += 1
out[t] = best
return out
def main():
t0 = time.time()
pairs, seats, mlast, plast = record_run()
print(f"the record run: {len(seats)} seats to {plast}, last m0 {mlast}"
f" ({time.time() - t0:.1f} s)")
print("CONTROLS")
bad = 0
for m, p, held in pairs[:150]:
mf = {q: 1 for q in held}
if (cgreedy.m0(mf) if mf else 3) != m:
bad += 1
check("C1 the door-formula m0 equals cgreedy.m0 on the first 150 seat"
" states", bad == 0, f"{bad} differ")
_, sseats = slack.record_run()
mine = [p for p in seats if p <= T]
theirs = [p for p in sseats if p <= T]
check("C2 the seats to 10^4 equal slack.py's", mine == theirs,
f"{len(mine)} seats")
check("C4 the last state read has m0 > 10^4", mlast > T,
f"m0 {mlast} after the seat {plast}")
pps = prime_powers(T)
pv = {s: p_of(s) for s, _, _ in pps}
E = hull([(m, R) for m, R, _ in pairs])
U = hull([(s, pv[s]) for s, _, _ in pps])
seated = set(seats)
S = hull([(s, pv[s]) for s, r, _ in pps if r in seated])
bpts = []
for s, r, a in pps:
pt = 4 * s if r == 2 else r * s
if pt <= T:
bpts.append((pt, pv[s]))
B = hull(bpts)
L, run = [0] * (T + 1), None
qs = [q for q in PRIMES if q <= 3 * T]
j = len(qs) - 1
for t in range(T, 0, -1):
while j >= 0 and qs[j] >= t:
v = p_of(qs[j])
run = v if run is None or v < run else run
j -= 1
L[t] = run
def p1(Ex):
return [t for t in range(1, T + 1) if Ex[t] > U[t]]
def p2(Ex):
return [t for t in range(1, T + 1)
if Ex[t] < S[t] or Ex[t] < B[t]]
def p2b(Ex):
return [t for t in range(1, T + 1) if Ex[t] < B[t]]
def p5(Ex):
over = [t for t in range(2, T + 1) if Ex[t] > max(S[t], B[t], t)]
off = [t for t in range(2, T + 1) if max(S[t], B[t]) >= t
and Ex[t] != max(S[t], B[t])]
return over, off
tb = max(range(1, T + 1), key=lambda t: (B[t], -t))
plant2 = list(E)
plant2[tb] = B[tb] - 1
plant1 = list(E)
plant1[5000] = U[5000] + 1
check("C3 P2's test flags E lowered below B at its largest value, P1's"
" flags E raised past U at t = 5000",
tb in p2b(plant2) and 5000 in p1(plant1) and B[2048] == 7681,
f"B's largest at t = {tb}; B(2048) = p(2^9) = {B[2048]}")
plant5 = list(E)
plant5[5000] += 1
check("C5 P5's test flags E raised by 1 at t = 5000",
all(5000 in x for x in p5(plant5)))
if not all(ok for _, ok in CHECKS):
print("CONTROL FAILED: nothing below is read.")
raise SystemExit(1)
print("THE ENVELOPES")
f1, f2 = p1(E), p2(E)
for t in (f1 + f2)[:5]:
print(f" E FAIL t = {t}: E {E[t]}, U {U[t]}, S {S[t]}, B {B[t]}")
check("P1 E <= U at every t <= 10^4", not f1)
check("P2 E >= S and E >= B at every t <= 10^4", not f2)
# P3: s* the prime power giving U(t), its prime r seated
arg = {}
best = (0, None)
for s, r, a in pps:
if pv[s] > best[0]:
best = (pv[s], (s, r))
arg[s] = best[1]
sstar, cur = [None] * (T + 1), None
for t in range(1, T + 1):
if t in pv:
cur = arg[t]
sstar[t] = cur
forced = [t for t in range(2, T + 1) if sstar[t] and sstar[t][1] in seated
and sstar[t][1] != 2]
bad3 = [t for t in forced if E[t] != U[t]]
check("P3 E = U at every t whose s* has its prime seated", not bad3,
f"{len(forced)} such t, {len(bad3)} off")
mt, ms = p5(E)
low = [t for t in range(2, T + 1) if max(S[t], B[t]) < t]
check("P5 E <= max(S, B, t) at every t, and E = max(S, B) wherever"
" max(S, B) >= t", not mt and not ms,
f"{len(mt)} and {len(ms)} t off; max(S, B) < t at {low}")
eq = sum(E[t] == U[t] for t in range(2, T + 1))
print("READINGS")
print(f" E = U at {eq} of {T - 1} t in 2..10^4")
off = [t for t in range(2, T + 1) if E[t] != U[t]]
kinds = {}
for t in off:
r = sstar[t][1]
k = "2" if r == 2 else ("seated" if r in seated else "skipped")
kinds[k] = kinds.get(k, 0) + 1
print(f" where E < U, the prime of s*: {kinds}; least E/U "
f"{min(E[t] / U[t] for t in range(3, T + 1)):.3f} over 3..10^4")
for name, F in (("E", E), ("U", U), ("S", S), ("B", B)):
tm = max(range(2, T + 1), key=lambda t: F[t] / t)
print(f" {name}(t)/t: largest {F[tm] / tm:.4f} = {F[tm]}/{tm}"
f"; at t = 10^4 {F[T]}")
print(f" E = S at {sum(E[t] == S[t] for t in range(2, T + 1))} t, "
f"B > S at {sum(B[t] > S[t] for t in range(2, T + 1))} t")
bl = sum(B[t] < L[t] for t in range(2, T + 1))
print(f" B < min p(q) over q >= t at {bl} of {T - 1} t; B/t <= 5 at "
f"{sum(B[t] <= 5 * t for t in range(2, T + 1))} t")
cross = [t for t in range(3, T + 1)
if (B[t] >= L[t]) != (B[t - 1] >= L[t - 1])]
print(f" B and min p(q) cross at {len(cross)} t, the last {cross[-1:]} ")
print("KILL")
print(" " + ("E KILL" if f1 or f2 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()