"""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()