#!/usr/bin/env python3 """Job 2612 / route 100: phase-refined translate bound D(P,p,L). For a primorial P, the twin-admissible slots A_P are r = kP + c, c in the alive classes mod P (c != 0,-2 mod every prime q | P). L consecutive A_P slots starting at alive class index phi have fixed offsets o_0=0,...,o_{L-1} from the first slot, so their residues mod a prime p (p !| P) are fixed up to a common shift s (the CRT translate of #1267). With k_phi(s) = #{i : o_i + s = 0 or -2 (mod p)}, #1267's argument gives drop = K*(P,R) - K*(Pp,R) <= min_s k_phi(s) for the phase phi of any maximal run. Hence drop <= D(P,p,L) := max_phi min_s k_phi(s), and D <= floor(2L/p) by pigeonhole (sum_s k_phi(s) = 2L). Output (stdout): one JSON object; exact integers only. """ import json, sys def primes_upto(n): return [q for q in range(2, n + 1) if all(q % d for d in range(2, int(q ** 0.5) + 1))] def alive(P): fs = [q for q in primes_upto(P) if P % q == 0] return [c for c in range(P) if all(c % q not in (0, (q - 2) % q) for q in fs)] def D(P, p, L, cls): m = len(cls); best = None; worst = None for phi in range(m): o = [((phi + i) // m) * P + cls[(phi + i) % m] - cls[phi] for i in range(L)] cnt = [0] * p for x in o: cnt[x % p] += 1 # translate s kills o with o+s = 0 or -2 mod p: residues -s and -s-2 k = min(cnt[(-s) % p] + cnt[(-s - 2) % p] for s in range(p)) best = k if best is None else max(best, k) worst = k if worst is None else min(worst, k) return best, worst def main(): Ps = [2, 6, 30, 210, 2310] Lmax = int(sys.argv[1]) if len(sys.argv) > 1 else 60 pmax = int(sys.argv[2]) if len(sys.argv) > 2 else 97 out = {"Lmax": Lmax, "pmax": pmax, "rows": 0, "strict": []} for P in Ps: cls = alive(P) for p in primes_upto(pmax): if P % p == 0: continue for L in range(1, Lmax + 1): fl = (2 * L) // p if fl == 0: continue d, dmin = D(P, p, L, cls) out["rows"] += 1 if d < fl: out["strict"].append([P, p, L, fl, d, dmin]) out["n_strict"] = len(out["strict"]) print(json.dumps(out, separators=(",", ":"))) if __name__ == "__main__": main()