"""probe_drop.py — light triage probe for route 100 (job 2609). Central uncertainty: does the sharp drop K*(Pp,R) >= K*(P,R) - 1 hold, or does a drop >= 2 exist? #1264 swept P=30 (p<=23, |R|<=3) and P in {210,2310} (|R|<=2), max drop = 1. This probe (i) reproduces the recorded counterexample, (ii) verifies the proven -1 upper bound on a small sample, (iii) extends the drop search to |R|=4 at P=30 and |R|=3 at P=210 (exact full-period K*), and (iv) checks the translate/ pigeonhole refinement: for p > K*(P,R) the drop is provably <= 1. Exact integer arithmetic only (Python ints; no floats in any decision). """ from __future__ import annotations from math import gcd, prod from itertools import combinations def primes_upto(n: int) -> list[int]: sieve = [True] * (n + 1) sieve[0] = sieve[1] = False for i in range(2, int(n ** 0.5) + 1): if sieve[i]: for j in range(i * i, n + 1, i): sieve[j] = False return [i for i in range(2, n + 1) if sieve[i]] def tile_slots(P: int) -> list[int]: return [r for r in range(P) if gcd(r, P) == 1 and gcd(r + 2, P) == 1] def longest_cyclic_run(seq) -> int: n = len(seq) if n == 0: return 0 best = cur = 0 for _ in range(2): for v in seq: if v: cur += 1 if cur > best: best = cur if best >= n: return n else: cur = 0 return best def Kstar(P: int, Q: list[int]) -> int: """Exact two-class covering run over full period M = P * prod(Q).""" Q = list(Q) if not Q: return 0 slots = tile_slots(P) D = len(slots) M = prod(Q) seq = bytearray(D * M) for k in range(M): for q in Q: shift = (k * P) % q t0 = (-shift) % q t2 = (-shift - 2) % q base = k * D for i, r in enumerate(slots): if not seq[base + i]: v = r % q if v == t0 or v == t2: seq[base + i] = 1 return longest_cyclic_run(seq) def main() -> None: print("=== (0) reproduce recorded counterexample (drop = 1) ===", flush=True) k30 = Kstar(30, [7, 11, 19]) k390 = Kstar(390, [7, 11, 19]) print(f"K*(30,{{7,11,19}}) = {k30}, K*(390,{{7,11,19}}) = {k390}, drop = {k30 - k390}", flush=True) print("\n=== (1) -1 upper bound, small sample (Lemma 4 sanity) ===", flush=True) viol = 0 total = 0 for P in (30, 210): for p in [q for q in primes_upto(23) if P % q != 0 and q >= 7]: Pp = P * p pool = [q for q in primes_upto(23) if q >= 7 and Pp % q != 0 and q != p] for r in range(0, 3): for R in combinations(pool, r): R = list(R) kPp = Kstar(Pp, R) kPp1 = Kstar(P, R + [p]) total += 1 if kPp > kPp1 - 1: viol += 1 print(f" -1 VIOLATION P={P} p={p} R={R}", flush=True) print(f" -1 bound: {total - viol}/{total} hold ({viol} violations)", flush=True) print("\n=== (2) drop search, P=30, p<=23, |R|<=4 (extends #1264's |R|<=3) ===", flush=True) max_drop = -10 ** 9 max_drop_ex = None drop_ge2 = [] hist = {} pleL_drop_ge2 = [] for p in [q for q in primes_upto(23) if 30 % q != 0]: Pp = 30 * p pool = [q for q in primes_upto(23) if q >= 7 and Pp % q != 0 and q != p] for r in range(0, 5): for R in combinations(pool, r): R = list(R) kP = Kstar(30, R) kPp = Kstar(Pp, R) drop = kP - kPp hist[drop] = hist.get(drop, 0) + 1 if drop > max_drop: max_drop = drop max_drop_ex = (p, R, kP, kPp) if drop >= 2: drop_ge2.append((p, R, kP, kPp)) if p <= kP: pleL_drop_ge2.append((p, R, kP, kPp)) print(f" P=30 (p<=23, |R|<=4): max drop = {max_drop} at {max_drop_ex}", flush=True) print(f" #(drop >= 2) = {len(drop_ge2)}; of those with p <= K*(P,R): {len(pleL_drop_ge2)}", flush=True) print(f" drop histogram: {dict(sorted(hist.items()))}", flush=True) print("\n=== (3) drop search, P=210, p in {11,13}, |R|<=3 (extends #1264's |R|<=2) ===", flush=True) max_drop2 = -10 ** 9 max_drop2_ex = None drop_ge2_2 = [] hist2 = {} for p in [11, 13]: Pp = 210 * p pool = [q for q in primes_upto(19) if q >= 11 and Pp % q != 0 and q != p] for r in range(0, 4): for R in combinations(pool, r): R = list(R) kP = Kstar(210, R) kPp = Kstar(Pp, R) drop = kP - kPp hist2[drop] = hist2.get(drop, 0) + 1 if drop > max_drop2: max_drop2 = drop max_drop2_ex = (p, R, kP, kPp) if drop >= 2: drop_ge2_2.append((p, R, kP, kPp)) print(f" P=210 (p in {{11,13}}, |R|<=3): max drop = {max_drop2} at {max_drop2_ex}", flush=True) print(f" #(drop >= 2) = {len(drop_ge2_2)}", flush=True) print(f" drop histogram: {dict(sorted(hist2.items()))}", flush=True) print("\n=== (4) translate/pigeonhole refinement check (p > L => drop <= 1) ===", flush=True) bad = 0 checked = 0 for P in (30, 210): for p in [q for q in primes_upto(23) if P % q != 0 and q >= 7]: Pp = P * p pool = [q for q in primes_upto(23) if q >= 7 and Pp % q != 0 and q != p] for r in range(0, 4): for R in combinations(pool, r): R = list(R) L = Kstar(P, R) if p <= L: continue kPp = Kstar(Pp, R) drop = L - kPp checked += 1 if drop > 1: bad += 1 print(f" REFINEMENT VIOLATION P={P} p={p} R={R} L={L} drop={drop}", flush=True) print(f" p > K*(P,R) cases checked: {checked}; drop > 1 found: {bad}", flush=True) if __name__ == "__main__": main()