"""slack.py -- a slack polynomial in the tide escapes the dam, and its square reaches breadth; the tide ceiling tau(P) is at least beta(P). QUESTION. Every c-greedy walk over Z is dammed: its support stays finite. Does a slack growing faster than linear in the tide escape, and does the tide ceiling tau(P) grow as a power of P with no hypothesis? DESIGN. Lam_P = lcm(p - 1 : p prime, p <= P), beta(P) the least prime power dividing no such p - 1 (the least element order unborn at P, in the birthday formula's sense), p(m) the least prime = 1 mod m. The f-greedy walk, f nondecreasing with f(t) >= t, takes at a state M any lambda-raising m <= f(m0(M)); c-greedy is f(t) = ct. A price, the least multiplier raising lambda at one prime q (the door lemma), is a power q^e with e > v_q(lambda), and the tide m0 is the least price. (1) THE RECORD RUN. From the void, read the odd primes in increasing order and seat each one whose p - 1 does not divide lambda, once. After every prime <= P is read the state M_P is odd and squarefree with lambda(M_P) = Lam_P, a skipped q having q - 1 | lambda when read. (2) THE FLOOR. m0(M_P) >= beta(P) for P >= 3: 2 unseated prices 2^(v + 3), a seated odd q prices q^(v + 1), a skipped q prices q^(v + 2), v = v_q(Lam_P), and a prime past P at least itself, a power of a prime dividing no p - 1 with p <= P. Each is a prime power not dividing Lam_P, so at least beta(P). Hence tau(P) >= beta(P). (3) THE ESCAPE. If f(t) >= p(t) at every prime power t, the record run is an f-greedy run seating infinitely many primes, each once (not breadth: 2 and the skipped primes stay out). The next seat R(P) is at most p(beta(P)), a prime past P (beta divides no p - 1, p <= P) whose p - 1 does not divide Lam_P, and p(beta) <= f(beta) <= f(m0(M_P)). By Linnik's theorem, p(m) <= C m^L at every m >= 2 for constants C and L, so f(t) = C t^L qualifies and beta(P) > (P/C)^(1/L); under GRH, p(m) << (m log m)^2. The script reads (2) and (3) at every prime P <= 10,000; the constants are the sources', no run reaches them. (4) BREADTH. If f(t) >= p(t)^2 at every prime power t, the f-greedy walk reaches breadth (the support every place) from the void. The RIDING RUN: m = 4 first (lambda 1 -> 2, 4 <= f(3)); then the records recomputed from lambda = 2, so 3 is skipped and the records run 5, 7, 11, ...; each record R is seated with the oldest skipped prime q not yet seated, m = R q, first in first out, or alone when none waits. q < R; a rider leaves lambda unchanged (q - 1 | lambda when skipped), so lambda stays Lam_P and m raises it through R. 2 at exponent 2 prices 2^(v + 1), a seated rider q^(v + 1), a waiting prime as in (2): every price is still a prime power not dividing lambda, the tide at least beta, and m < R^2 <= p(beta)^2 <= f(m0). Records never end, so every skipped prime rides at a finite step: support every place, every exponent finite. By Linnik f(t) = C^2 t^(2L). (5) SEEDS. Neither (3) nor (4) holds from every seed: at 3^N with 3^N >= f(3), 3's own part tops lambda's, so 3 prices 3^(v - a + 2) = 3, the tide is at most 3 and every move at most f(3); a prime r lifts v_3(lambda) past 3's own part only if 3^N | r - 1, so r > f(3), and no move brings one: every f-greedy walk is dammed there, whatever f. BY HAND. P = 13: Lam = 60, beta = 7; the record run seats 3, 5, 7, 11 and skips 13; at M_13 = 1155 the prices are 2^5, 9, 25, 7, 11, 13^2 and 17, m0 = 7 = beta; R(13) = 17 <= p(7) = 29. P = 7: M = 105, lambda 12, m0 = 5, R = 11. The riding run: from the void (lambda 1, beta 2, m0 3) the move 4; at 4 (lambda 2, beta 3, m0 4) the move 15 = 5*3; at 60 (lambda 4, beta 3, m0 3) the move 7; at 420 (lambda 12, beta 5, m0 5) the move 11; at 4620 (lambda 60, beta 7, m0 7, 13 waiting) the move 221 = 17*13 <= p(7)^2 = 841. PREDICTIONS (frozen before the code). P1 m0(M_P) >= beta(P) and tau(P) >= beta(P) at every prime 3 <= P <= 10,000 (forced). P2 R(P) <= p(beta(P)) at every such P (forced). P3 The riding run, at the move 4 and at every move whose record R is <= 10,000: the move raises lambda, m0 >= beta on the state before it, R <= p(beta), m <= p(beta)^2, a rider q < R with q - 1 | lambda (forced). P4 Its records from 5 on are the record run's (forced: lambda agrees from 2 on). KILL. "C1 FAIL" printed at a P where P1 or P2 breaks ends (2) or (3) as stated; "C3 FAIL" at a move where P3 breaks ends (4). CONTROLS, read first. C0: the hand values at 13 and 7, and the riding run's first five moves with their tides and betas. C4: P3's test must flag two planted breaks, the fifth move's rider moved alone (it does not raise lambda) and a rider past its record (the least prime past it with q - 1 | lambda, so only q < R fails). C2, read after the gate, the edge: m0 = beta at P = 13, so P1's inequality is met with equality and is not slack by construction; the count of P at equality is printed. FINDINGS (from the printed run; the controls passed first). KILL silent: P1 and P2 hold at all 1228 primes 3 <= P <= 10,000, every R(P) found below X + 200; m0 = beta at 1149 of the 1228, the last at 9973. At P = 101, 1009, 2003, 5003, 9973: beta 17, 109, 167, 227, 361; tau 47, 227, 383, 839, 1823; R 103, 1019, 2027, 5087, 10007; p(beta) 103, 1091, 2339, 5449, 10831. tau/beta = 5.0499 at 9973; ln beta / ln P over [1000, 10^4] is least 0.6307, at P = 5443. The record run's slack R/m0 reaches 27.720 at 9973, nearly P/beta by construction, and 1.1595 times ln^2 m0 at P = 181, so no polylog rate is claimed. P3 holds at all 302 riding moves, the move 4 and the 301 records 5 to 9887, the records the record run's (P4); the riders leave in the order queued, and once every prime <= 10,000 is read, 927 are queued, 296 ridden and 631 waiting, the least 2897, so every skipped prime below 2897 has ridden. C4 flags both planted breaks. RUN RECORD. 10/10 checks, 0.6 s, peak commit 55.3 MB. """ import os import sys import time from math import log os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import growth # noqa: E402 import cgreedy # noqa: E402 CHECKS = [] X = cgreedy.X PR = cgreedy.PR # the primes to X + 200 PM1 = cgreedy.PM1 SIEVE = 4_000_000 def check(name, ok, detail=""): CHECKS.append((name, bool(ok))) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) def sieve(): s = bytearray([1]) * SIEVE s[0] = s[1] = 0 for i in range(2, int(SIEVE ** 0.5) + 1): if s[i]: s[i * i::i] = bytearray(len(s[i * i::i])) return s def least_prime_1(m, isp): """p(m), the least prime = 1 mod m, off the sieve.""" n = m + 1 while not isp[n]: n += m if n >= SIEVE: raise SystemExit(f"sieve too short for p({m})") return n def beta_of(vN, pps): """The least prime power q = r^a with a > v_r(Lam); pps holds (q, r, a).""" for q, r, a in pps: if vN.get(r, 0) < a: return q raise SystemExit("no unborn prime power in range") def prime_powers(n): """Every prime power q <= n as (q, r, a), q = r^a, in order.""" out = [] for r in PR: 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 record_run(): """At every prime P <= X: (seated set, the exponents of Lam_P), and the run's seats in order.""" vN, seated, seats, out = {}, [], [], {} for p in PR: if p > 2 and not growth.divides(PM1[p], vN): seated.append(p) seats.append(p) for r, e in PM1[p].items(): if e > vN.get(r, 0): vN[r] = e if p <= X: out[p] = (list(seated), dict(vN)) return out, seats def riding_run(): """The run of (4): 4 from the void, then each record R with the oldest queued prime q. The moves as (state before, m, R, q), the primes in the order queued, and the queue when R passes X.""" mf, moves, queue, queued = {2: 2}, [({}, 4, None, None)], [], [] lf = cgreedy.lam(mf) for p in PR: if p == 2: continue if growth.divides(PM1[p], lf): queue.append(p) queued.append(p) continue if p > X: break q = queue.pop(0) if queue else None moves.append((dict(mf), p * (q or 1), p, q)) mf = growth.merge_add(mf, {p: 1, **({q: 1} if q else {})}) lf = cgreedy.lam(mf) return moves, queued, queue def riding_rows(moves, pps, isp): """Per move: (m, m0, beta) and the moves breaking P3.""" rows, bad = [], [] for M, m, R, q in moves: lf = cgreedy.lam(M) b = beta_of(lf, pps) t = cgreedy.m0(M) pb = least_prime_1(b, isp) ok = (cgreedy.raises(M, lf, m) and t >= b and m <= pb * pb and (R is None or R <= pb) and (q is None or (q < R and growth.divides(PM1[q], lf)))) rows.append((m, t, b)) if not ok: bad.append((m, R, q, t, b, pb)) return rows, bad def section_controls(row, run, rows, moves, pps, isp): print("CONTROLS") b, m0, t, R, pb = row[13] check("C0 at 13: beta 7, m0 7, R 17, p(7) 29 (by hand)", (b, m0, R, pb) == (7, 7, 17, 29), f"{b}, {m0}, {R}, {pb}") b, m0, t, R, pb = row[7] check("C0 at 7: m0 5, R 11 (by hand)", (m0, R) == (5, 11), f"{m0}, {R}") check("C0 M_13 is 3*5*7*11", run[13][0] == [3, 5, 7, 11], f"{run[13][0]}") check("C0 the riding run's first moves 4, 15, 7, 11, 221, tides " "3, 4, 3, 5, 7, beta 2, 3, 3, 5, 7 (by hand)", rows[:5] == [(4, 3, 2), (15, 4, 3), (7, 3, 3), (11, 5, 5), (221, 7, 7)], f"{rows[:5]}") M, m, R, q = moves[4] lf = cgreedy.lam(M) nxt = next(p for p in PR if p > R and growth.divides(PM1[p], lf)) plants = [(M, q, R, q), (M, R * nxt, R, nxt)] caught = len(riding_rows(plants, pps, isp)[1]) check(f"C4 P3 flags a rider moved alone and the rider {nxt} past its " f"record {R}", caught == 2, f"{caught} of 2 flagged") def section_record(row): """The floor (2) and the escape (3) at every prime 3 <= P <= X.""" print("THE FLOOR AND THE ESCAPE") f1 = [P for P in row if not (row[P][1] >= row[P][0] and row[P][2] >= row[P][0])] f2 = [P for P in row if row[P][3] is not None and row[P][3] > row[P][4]] for P in (f1 + f2)[:5]: print(f" C1 FAIL {P}: {row[P]}") check(f"P1 m0(M_P) >= beta and tau >= beta at every prime " f"3 <= P <= {X}", not f1, f"{len(row)} primes") known = [P for P in row if row[P][3] is not None] check("P2 R(P) <= p(beta(P)) wherever R(P) <= X + 200", not f2, f"{len(known)} primes") eq = [P for P in row if row[P][1] == row[P][0]] check("C2 m0 = beta at 13 (the edge; C0 already fixed it)", 13 in eq, f"{len(eq)} primes at equality, the last {eq[-1]}") print(" P beta m0 tau R p(beta) slack") for P in [7, 13, 101, 1009, 2003, 5003, 9973]: b, m0, t, R, pb = row[P] sl = f"{R / m0:6.3f}" if R else " - " print(f" {P:5d} {b:6d} {m0:6d} {t:6d} {R or 0:6d} {pb:8d} {sl}") print("READINGS") sl = max((row[P][3] / row[P][1], P) for P in known) print(f" the largest slack R/m0: {sl[0]:.4f} at P = {sl[1]}") hi = max((row[P][3] / row[P][1] / log(row[P][1]) ** 2, P) for P in known if P >= 100) print(f" R/m0 over ln^2 m0 on [100, 10^4]: most {hi[0]:.4f} at " f"P = {hi[1]}") print(f" tau/beta at 9973: {row[9973][2] / row[9973][0]:.4f}") lb = min((log(row[P][0]) / log(P), P) for P in row if P >= 1000) print(f" ln beta / ln P over [1000, 10^4]: least {lb[0]:.4f} at " f"P = {lb[1]}") return bool(f1 or f2) def section_riding(moves, queued, queue, bad, seats): """Breadth (4): the riding run's moves with record <= X.""" print("BREADTH: THE RIDING RUN") for r in bad[:5]: print(f" C3 FAIL move {r[0]} (R {r[1]}, q {r[2]}): m0 {r[3]}, " f"beta {r[4]}, p(beta) {r[5]}") check(f"P3 every riding move with R <= {X} raises lambda, m0 >= beta, " f"R <= p(beta), m <= p(beta)^2, riders q < R, q - 1 | lambda", not bad, f"{len(moves)} moves") recs = [R for _, _, R, _ in moves if R] check("P4 its records are the record run's from 5 on", recs == [p for p in seats if 5 <= p <= X], f"{len(recs)} records, {recs[0]} to {recs[-1]}") riders = [q for _, _, _, q in moves if q] print(f" riders leave in the order queued: " f"{riders == queued[:len(riders)]}; with every prime <= {X} " f"read, {len(queued)} queued, " f"{len(riders)} ridden, {len(queue)} waiting, the least {queue[0]}") return bool(bad) def main(): t0 = time.time() isp = sieve() pps = prime_powers(X) run, seats = record_run() tab = cgreedy.tau_table() row = {} for P in PR: if P < 3 or P > X: continue seated, vN = run[P] m0 = cgreedy.m0({q: 1 for q in seated}) nxt = [q for q in seats if q > P] b = beta_of(vN, pps) row[P] = (b, m0, tab[P][0], nxt[0] if nxt else None, least_prime_1(b, isp)) moves, queued, queue = riding_run() rows, bad = riding_rows(moves, pps, isp) section_controls(row, run, rows, moves, pps, isp) if not all(ok for _, ok in CHECKS): print("CONTROL FAILED: nothing below is read.") raise SystemExit(1) fired = section_record(row) fired = section_riding(moves, queued, queue, bad, seats) or fired print("KILL") print(f" {'FIRED' if fired 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()