#!/usr/bin/env python3 """job2723 — exact K* plus proven upper bounds on the two-class covering run. Object (route-023 / route-026, corpus conventions) -------------------------------------------------- P : tile modulus (a primorial product), tile T_P = { r in [0,P) : gcd(r,P) = gcd(r+2,P) = 1 }. q kills r : q | r or q | r+2. K*(P,Q) : longest run of CONSECUTIVE slots of T_P (index-consecutive in the sorted slot list, over the full period M = P*prod(Q)) each killed by some q in Q. Two independent exact engines are provided and cross-checked: * exact_fullperiod -- materialises the full period (small cases only); * exact_blocksplit -- block/phase decomposition with explicit CRT, O(D*prod(Q)) arithmetic but no period-long materialisation beyond the small block list. Proven upper bounds (proofs in the report, both elementary) (U1) density bound K* <= 2*D*prod(Q) / M fails trivially; not used. (U2) *density/gap bound*: let G = max gap between consecutive slots of T_P (cyclic, full period). Then K* <= (Sum_q (G/q + 2)) / (1 - G*Sum_q (1/q)) ... (GAP) whenever the denominator is positive. (U3) trivial-run bound: K* <= number of available killers in a window, only when every q kills at most one run position. All arithmetic is exact integer arithmetic; no floating point enters a decision. """ from __future__ import annotations from math import gcd, prod from fractions import Fraction # ---------------------------------------------------------------- primorials def primes_upto(n: int) -> list[int]: if n < 2: return [] s = bytearray([1]) * (n + 1) s[0] = s[1] = 0 i = 2 while i * i <= n: if s[i]: s[i * i::i] = bytearray(len(range(i * i, n + 1, i))) i += 1 return [i for i in range(2, n + 1) if s[i]] def primorial(x: int) -> int: return prod(primes_upto(x)) 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] # ------------------------------------------------------- exact engine A: full def exact_fullperiod(P: int, Q) -> int: """Longest cyclic run of consecutive slots killed by some q in Q. Materialises the full period P*prod(Q). Small P,Q only. """ Q = sorted(Q) slots = tile_slots(P) if not slots: return 0 D = len(slots) M = prod(Q) total = D * M killed = bytearray(total) for k in range(M): base = k * D for q in Q: sh = (k * P) % q t0 = (-sh) % q t2 = (-sh - 2) % q for i, r in enumerate(slots): v = r % q if v == t0 or v == t2: killed[base + i] = 1 # longest cyclic run best = cur = 0 for _ in range(2): for v in killed: if v: cur += 1 if cur > best: best = cur else: cur = 0 return min(best, total) # --------------------------------------------- exact engine B: block/phase CRT def exact_blocksplit(P: int, Q, L: int) -> bool: """Feasibility of a killed run of length L, by the block/phase CRT reading. Within block k the kill condition for q is r in {a_q(k), a_q(k)-2} with a_q(k) = (-kP) mod q. A run of length L has all L slots killed; this is a small exact search over block indices with a DFS on unresolved primes. Returns True iff such a run exists in the full period. """ Q = sorted(Q) slots = tile_slots(P) if not slots or L <= 0: return L <= 0 D = len(slots) M = prod(Q) killed_mod = {} for q in Q: killed_mod[q] = {(0), (q - 2)} for k in range(M): sh = (k * P) % Q[0] if False else None # keep structure explicit below # collect kill sets per q for this block kills = [] for q in Q: sh = (k * P) % q t0 = (-sh) % q t2 = (-sh - 2) % q kills.append((q, t0, t2)) # sliding window over slot indices for i in range(D): ok = True for j in range(L): r = slots[(i + j) % D] hit = False for q, t0, t2 in kills: v = r % q if v == t0 or v == t2: hit = True break if not hit: ok = False break if ok: return True return False # ------------------------------------------------------------------- bounds def max_slot_gap(P: int) -> int: """G = maximum cyclic gap between consecutive slots of T_P over the period P.""" s = tile_slots(P) if len(s) < 2: return 0 g = [s[i + 1] - s[i] for i in range(len(s) - 1)] g.append(s[0] + P - s[-1]) return max(g) def gap_bound(P: int, Q) -> int: """Proven upper bound (GAP): K* <= ceil( (Sum_q (G/q+2)) / (1 - G*Sum_q 1/q) ). Returns -1 (meaning "no information") when the denominator is not positive. Exact rationals throughout; the ceiling is taken only at the end. """ G = Fraction(max_slot_gap(P)) if G == 0: return 0 num = sum(G / q + 2 for q in Q) den = 1 - G * sum(Fraction(1, q) for q in Q) if den <= 0: return -1 val = num / den return -(-val.numerator // val.denominator) # ceil def density_bound(P: int, Q) -> int: """Elementary: a run of L killed slots needs L <= (number of slots in the period).""" return len(tile_slots(P)) * prod(Q) # --------------------------------------------------------------------- corridor def corridor(s: int): """Corpus corridor: P = prod_{p < s} p, Q = { q : s < q <= 2s }.""" P = primorial(s - 1) if s - 1 >= 2 else 1 Q = [q for q in primes_upto(2 * s) if q > s] return P, Q