slack.py

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