anchor.py

"""anchor.py -- does a run that chooses its seats by their anchors stay
below the record run against the dam's bar F?

QUESTION. E/F peaks at 7.6829 at t = 1997 (fwide.py), where the record
and the skipping run both pay p(1997) = 87869. Does a run that weighs
each seat by the anchor it will owe stay below that peak?

DESIGN. choosy.py's engine and tide: one odd prime per move, exponent 1,
2 never seated, read until the tide m0 passes 10^4. F from fwide.py's
widened table, fixed at every t in 4..10^4, read at max(t, 4). At each
move the class is the primes = 1 mod s, s the tide's unborn power (m0 at
a seated r, m0/r at a skipped one, m0/4 at 2, m* at an open r, m* the
part of r - 1 not dividing lambda); every class prime is past m0 (one
below would be open, priced under m0), and at an open r the least is r.
  L1 seats the class prime with least p(P), ties to the least P; the
     candidates are the class primes below p(P0), P0 the least.
  LV seats the class prime with least max(P/F(m0), V(P)), ties to the
     least P; candidates until P/F(m0) reaches the best score.
(a) THE ANCHOR BAR, by hand: the tide never falls, since lambda only
grows, so no other price falls, and the seat's new price is at least
P >= m0. Every
seat P raises lambda, so it was priced at most P and came from a tide
<= P. If no held prime is 1 mod P,
the price at P is P and the tide stays at most P until one enters, at
least p(P) (if none ever does, the run's endless new primes all come
from a tide <= P, the run being endless); if one is held, it entered from a tide <= P. So E_run(P) >=
p(P) at every seat P.
(b) By hand: at the skipping run's tide-167 state (m* = 83) the class
is 167, 499, 997, ...; p(167) = 2339, p(499) = 1997, and every class
prime from 997 on has p(P) > 1997; L1 seats 499, whose anchor is 1997,
whose anchor is p(1997) = 87869.
(c) The chain value: V(q) = min over primes a = 1 mod q of
max(a/F(q), V(a)), V(q) = 0 past 10^4. An anchor a of q comes from a
tide <= q, so a/F(q) <= E_run(q)/F(q) along the chain a run follows.

PREDICTIONS (frozen before the code).
P1 (forced) the engine under choosy's arms A and B gives their seats.
P2 (proved, (a)) E_run(P) >= p(P) at every seat P <= 10^4, both arms.
P3 (proved) F <= E_run at every t in 4..10^4, both arms.
P4 (a guess, 65%) L1 has E(1997) = 87869 or max E/F >= 7.6829.
P5 (a guess, 55%) LV has max E/F < 7.6829 and E(1997) < 87869.

THE PRINT. Per arm: max E_run/F over 4..10^4 with its t, and
E_run(1997). "ANCHOR CHOICE MOVES THE PRICE: <arms>" for the arms with
max E_run/F below the record run's and E_run(1997) < 87869, else
"KILL: NO ARM BELOW THE RECORD RUN". The second clause is implied by
the first, p(1997)/F(1997) being the record run's peak itself.

CONTROLS, read first. C1 is P1 (and arm A's envelope is E). C2 L1's
chooser at the skipping run's tide-167 state seats 499, by (b). C3 the
kill's reading passes F and fails F planted at 8 F at one t. C4 P2's
test flags E_run lowered to p(P) - 1 at one seat P.

FINDINGS (from the printed run; the controls passed first). C1: the
engine gives choosy's arm A (519 seats) and arm B (425) exactly, and
arm A's envelope is E. C2: m* = 83, L1 seats 499. P2 and P3 hold on both
arms. P4 holds: L1's max E_run/F is 22.0322 at t = 1319 (E_run 129263 =
98 * 1319 + 1, F 5867), E_run(1997) 129263; it never seats 1997.
P5 holds: LV's max E_run/F is 6.7315 at t = 361 (E_run 10831, F 1609),
E_run(1997) = 14591; it never seats 1997. THE PRINT: ANCHOR CHOICE
MOVES THE PRICE: LV; the kill is silent.
LV: 417 seats, 175 held primes <= 10^4, 242 seats past 10^4, the
largest 153757. L1: 470 seats, 257 held primes <= 10^4. Five dear
primes q <= 10^4 have p(q)/F(q) >= 7.6829: 1997, 2053, 5227, 5641, 6637.
V(1997) = 7.6829, V(499) = 4.7881, V(167) = 3.6376.
Readings added after the first run: LV = F at 1491 t in 4..10^4, 1458 of
them >= 100, every t in 8543..10^4: at tide 8543 (open, m* = 4271) LV
seats 153757 = 36 * 4271 + 1, which is F(8543), F(8542) being 121697.
E_LV/F over t >= 100 has median 2.0702; E_LV < E at 9317 t and > E at
28 t in 4..10^4. LV misses F first at 7, 8, 9, 10, 17.
Readings added after the second run: L1 never stands at the open 167 of
(b) (open at 167: False); its peak is another failure, at tide 1319 (seated,
s = 1319) it seats 129263, p(P) = 258527, over the least class prime
23743, p(P0) = 284917: least p(P) overpays the seat to cheapen the next
anchor. Added with the second audit: E, E_B and E_LV are all above F
first at t = 25 (then 26..29), at 8492 t in 4..10^4; below 25 one of
them meets F at every t.
So a run choosing each seat by the chain of anchors it will owe stays
within 6.7315 F to 10^4, below the record run's 7.6829, and meets F
at 1491 of the 9997 t: there the least envelope over escaping runs
is F itself (LV, continued past its tide 10^4 by the record rule,
seating the least open prime r, from a tide <= r, keeps its tide
nondecreasing by (a) and a new prime at every move, so escapes; moves
from tides past t do not count at t).
RUN RECORD. First run: the dear-prime reading read F at q = 3, where it
is unset, and was given F(max(q, 4)), the prints above it unchanged.
10/10, 37.3 s, 60.5 MB. With the readings: 10/10, 37.2 s, 60.4 MB.
P1 and C3 as frozen read the record policy's E and an arm planted at
8 F; before the first run they became choosy's arms A and B and F
planted at 8 F, each at least as strict. With the last readings, the
monotone tide in (a) and the guard on LV's top run: 10/10, 37.3 s,
60.4 MB. With the second audit's reading: 10/10, 36.9 s, 61.5 MB.
Run from code/: 10/10, 40.4 s, 60.4 MB.

    python anchor.py
"""

import os
import time

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import growth  # noqa: E402
import envelope as ev  # noqa: E402
import choosy  # noqa: E402
import dambar  # noqa: E402
import fwide  # noqa: E402

T = ev.T
CHECKS = []


def check(name, ok, detail=""):
    CHECKS.append((name, bool(ok)))
    print(f"  [{'PASS' if ok else 'FAIL'}] {name}"
          + (f" -- {detail}" if detail else ""))


def isp(n):
    return ev.SPF[n] == n if n <= ev.N else growth.is_prime(n)


def cls(s):
    """The primes = 1 mod s, increasing."""
    n = s + 1
    while True:
        if isp(n):
            yield n
        n += s


def modulus(m0, r, kind, vN):
    if kind == "seated":
        return m0
    if kind == "skipped":
        return m0 // r
    if kind == "two":
        return m0 // 4
    ms = 1
    for q, e in ev.fac(r - 1).items():
        if e > vN.get(q, 0):
            ms *= q ** e
    return ms


def make_v(F):
    memo = {}

    def V(q):
        if q > T:
            return 0.0
        if q not in memo:
            best = None
            for a in cls(q):
                x = a / F[max(q, 4)]
                if best is not None and x >= best:
                    break
                v = max(x, V(a))
                if best is None or v < best:
                    best = v
            memo[q] = best
        return memo[q]
    return V


def pick_a(m0, r, kind, s, F, V):
    return next(cls(s))


def pick_b(m0, r, kind, s, F, V):
    g = cls(s)
    P = next(g)
    return next(g) if kind == "open" else P


def pick_l1(m0, r, kind, s, F, V):
    best = None
    for P in cls(s):
        if best is not None and P >= best[0]:
            break
        key = (ev.p_of(P), P)
        if best is None or key < best:
            best = key
    return best[1]


def pick_lv(m0, r, kind, s, F, V):
    f = F[max(m0, 4)]
    best = None
    for P in cls(s):
        if best is not None and P / f >= best[0]:
            break
        key = (max(P / f, V(P)), P)
        if best is None or key < best:
            best = key
    return best[1]


def run(pick, F, V, stop=None, log=None):
    """[(m0, seat)] until m0 > T; with stop=(m0, kind), the state
    (held, vN, r, s) at the first tide matching it instead; log gathers
    (m0, kind, s) per move."""
    held, vN, pairs = set(), {}, []
    while True:
        m0, r, kind = choosy.tide(held, vN)
        if m0 > T:
            return pairs
        s = modulus(m0, r, kind, vN)
        if stop and (m0, kind) == stop:
            return held, vN, r, s
        P = pick(m0, r, kind, s, F, V)
        if log is not None:
            log.append((m0, kind, s))
        assert P not in held and P > 2 and (P - 1) % s == 0
        pairs.append((m0, P))
        held.add(P)
        for q, e in choosy.factor(P - 1).items():
            if e > vN.get(q, 0):
                vN[q] = e


def main():
    t0 = time.time()
    fwide.widen(fwide.PMAX)
    F = dambar.f_table(fwide.tau_wide(fwide.PMAX, T))
    ts = range(4, T + 1)
    assert all(F[t] is not None for t in ts)
    print(f"F fixed on 4..{T} ({time.time() - t0:.1f} s)")
    V = make_v(F)
    epairs, _, _, _ = ev.record_run()
    E = ev.hull([(m, R) for m, R, _ in epairs])
    rec = max(E[t] / F[t] for t in ts)
    p1997 = ev.p_of(1997)

    def passes(Ex):
        return max(Ex[t] / F[t] for t in ts) < rec and Ex[1997] < p1997

    def p2_bad(Ex, seats):
        return [P for P in seats if P <= T and Ex[P] < ev.p_of(P)]

    print("CONTROLS")
    out = {}
    for name, pick in (("A", pick_a), ("B", pick_b)):
        mine = run(pick, F, V)
        theirs, _ = choosy.run(name)
        out[name] = mine
        check(f"C1 the engine under arm {name} gives choosy's seats",
              mine == theirs, f"{len(mine)} seats, {len(theirs)} choosy's")
    EA = ev.hull(out["A"])
    check("C1 arm A's envelope is E at every t <= 10^4",
          all(EA[t] == E[t] for t in range(T + 1)))
    held, vN, r, s = run(pick_b, F, V, stop=(167, "open"))
    got = pick_l1(167, r, "open", s, F, V)
    check("C2 L1 at the skipping run's tide-167 state seats 499",
          got == 499 and s == 83, f"m* = {s}, seat {got}")
    plant = list(F)
    plant[500] = 8 * F[500]
    check("C3 the kill's reading passes F and fails F planted at 8 F",
          passes(F) and not passes(plant), f"record bar {rec:.4f}")
    seats = [P for _, P in out["A"]]
    Pp = max(P for P in seats if P <= T)
    plant = list(EA)
    plant[Pp] = ev.p_of(Pp) - 1
    check("C4 P2's test flags E_run lowered to p(P) - 1 at one seat",
          Pp in p2_bad(plant, seats) and not p2_bad(EA, seats),
          f"P = {Pp}")
    if not all(ok for _, ok in CHECKS):
        print("CONTROL FAILED: nothing below is read.")
        raise SystemExit(1)

    print("THE ARMS")
    res = {}
    for name, pick in (("L1", pick_l1), ("LV", pick_lv)):
        t1 = time.time()
        log = []
        pairs = run(pick, F, V, log=log)
        Ex = ev.hull(pairs)
        seats = [P for _, P in pairs]
        res[name] = (pairs, Ex, log)
        bad = p2_bad(Ex, seats)
        check(f"P2 {name}: E_run(P) >= p(P) at every seat P <= {T}",
              not bad, f"{len(bad)} off {bad[:3]}")
        under = [t for t in ts if Ex[t] < F[t]]
        check(f"P3 {name}: F <= E_run on 4..{T}", not under,
              f"{len(under)} off {under[:3]}")
        print(f"  {name}: {len(pairs)} seats, "
              f"{sum(P <= T for P in seats)} held primes <= {T}, "
              f"E_run({T})/F {Ex[T] / F[T]:.4f} ({time.time() - t1:.1f} s)")
        if 1997 in seats:
            i = seats.index(1997)
            print(f"  {name}: 1997 seated at move {i} from tide "
                  f"{pairs[i][0]}")

    print("READINGS")
    dear = [q for q in ev.PRIMES if 3 <= q <= T
            and ev.p_of(q) / F[max(q, 4)] >= rec]
    print(f"  dear primes (p(q)/F(q) >= {rec:.4f}), q <= {T}: "
          f"{len(dear)}, first {dear[:8]}")
    print(f"  V(1997) {V(1997):.4f}, V(499) {V(499):.4f}, "
          f"V(167) {V(167):.4f}")
    # added after the first run: where LV meets F, LV against E, and
    # LV's seat at the tide where F takes its last jump
    pairs, Ex, log = res["LV"]
    eq = [t for t in ts if Ex[t] == F[t]]
    top = T if Ex[T] == F[T] else T + 1
    while top > 4 and Ex[top - 1] == F[top - 1]:
        top -= 1
    print(f"  LV = F at {len(eq)} t in 4..{T}, {sum(t >= 100 for t in eq)}"
          f" of them >= 100, every t in "
          + (f"{top}..{T}" if top <= T else "none at the top"))
    r = sorted(Ex[t] / F[t] for t in ts if t >= 100)
    print(f"  E_LV/F over t >= 100: median {r[len(r) // 2]:.4f}; E_LV < E at"
          f" {sum(Ex[t] < E[t] for t in ts)} t, > E at "
          f"{sum(Ex[t] > E[t] for t in ts)} t in 4..{T}")
    for (m0, kind, s), (_, P) in zip(log, pairs):
        if m0 == top:
            print(f"  LV at tide {m0} ({kind}, s = {s}) seats {P} = "
                  f"{(P - 1) // s} s + 1; F({m0 - 1}) {F[m0 - 1]}, "
                  f"F({m0}) {F[m0]}")
    print(f"  LV seats past {T}: {sum(P > T for _, P in pairs)}, largest "
          f"{max(P for _, P in pairs)}")
    print(f"  LV misses F first at {[t for t in ts if Ex[t] != F[t]][:5]}")
    # added with the second audit: where no run read here meets F
    EB = ev.hull(out["B"])
    none = [t for t in ts if min(E[t], EB[t], Ex[t]) > F[t]]
    print(f"  E, E_B and E_LV all above F first at {none[:5]}; "
          f"{len(none)} t in 4..{T}")
    # added after the second run: what L1 seats at its peak, against the least
    # class prime there, and whether it ever stands at an open 167
    pairs, Ex, log = res["L1"]
    tm = max(ts, key=lambda t: Ex[t] / F[t])
    for (m0, kind, s), (_, P) in zip(log, pairs):
        if P == Ex[tm]:
            P0 = next(cls(s))
            print(f"  L1 at tide {m0} ({kind}, s = {s}) seats {P}, p(P) "
                  f"{ev.p_of(P)}; least class prime {P0}, p(P0) "
                  f"{ev.p_of(P0)}")
    print(f"  L1 seats 167: {167 in [P for _, P in pairs]}; open at 167: "
          f"{(167, 'open') in [(m, k) for m, k, _ in log]}")

    print("THE PRINT")
    ok = []
    for name in ("L1", "LV"):
        Ex = res[name][1]
        tm = max(ts, key=lambda t: Ex[t] / F[t])
        print(f"  {name}: max E_run/F {Ex[tm] / F[tm]:.4f} at t = {tm} "
              f"(E_run {Ex[tm]}, F {F[tm]}); E_run(1997) {Ex[1997]}")
        if passes(Ex):
            ok.append(name)
    print("  " + (f"ANCHOR CHOICE MOVES THE PRICE: {', '.join(ok)}" if ok
                  else "KILL: NO ARM BELOW THE RECORD RUN"))
    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()