#!/usr/bin/env python3 """ Job #1013 (route 3): endpoint-safe fixed-gap CRT gate, run level by level. A position n starts a G-gap of T_x iff (a) n and n+G are slots: n != 0,-2 and n != -G,-(G+2) (mod p) for p <= x; (b) every interior n+6i, i = 1..G/6-1, is NOT a slot. Slots are coprime to 2,3 automatically once n = 5 (mod 6), so the free phases are p = 5..x. Freeze a_p = n mod p; the kill mask of a_p is M(p,a) = { i : a+6i = 0 or -2 (mod p) }, and (b) is union_p M(p,a_p) = {1..G/6-1}. One phase per prime is enumerated by exact uncovered-bitmask DFS with unit propagation and two safe prunes (union and count). Leaves are CRT-reconstructed with n = 5 (mod 6), deduplicated, and every reconstructed span is re-checked by direct trial division, independently of the mask machinery: the gate never searches for a maximum and never scans a period. Usage: g2-fixed-gap-crt.py [x ...] (default: every published level, 13..31) stdout: the result. stderr: timing/rate lines only. """ import sys import time from collections import Counter T0 = time.time() def log(*a): print(*a, file=sys.stderr) ALLP = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43] # level x -> (published G2(x#), published least position, published multiplicity) PUB = { 13: (66, 731, 12), 17: (108, 701, 20), 19: (150, 659, 20), 23: (204, 76166567, 4), 29: (258, 1205437109, 2), 31: (348, 8813641451, 4), 37: (528, 544899485411, 2), 41: (546, 3784200788231, 4), 43: (618, 830330079152051, 8), } def popcount(x): return bin(x).count("1") def run_level(X): G, LEAST, NMAX = PUB[X] PRIMES = [p for p in ALLP if 5 <= p <= X] NOFF = G // 6 - 1 PRIMORIAL = 1 for p in ALLP: if p <= X: PRIMORIAL *= p PREV = max([p for p in ALLP if p < X] + [3]) # previous primorial level FULL = (1 << NOFF) - 1 def forb(p): return {(0) % p, (-2) % p, (-G) % p, (-(G + 2)) % p} allow = {p: [a for a in range(p) if a not in forb(p)] for p in PRIMES} mask = {} for p in PRIMES: for a in allow[p]: m = 0 for i in range(1, NOFF + 1): if (a + 6 * i) % p == 0 or (a + 6 * i + 2) % p == 0: m |= 1 << (i - 1) mask[(p, a)] = m cands = [[0] * len(PRIMES) for _ in range(NOFF + 1)] for i in range(1, NOFF + 1): for j, p in enumerate(PRIMES): b = 0 for t in ((-6 * i) % p, (-6 * i - 2) % p): if t in allow[p]: b |= 1 << t cands[i][j] = b nodes = [0] solutions = [] def propagate(dom, rem, cover, assign): dom = dict(dom) rem = set(rem) assign = dict(assign) while True: U = FULL & ~cover cap = 0 for j in rem: best = 0 for a in allow[PRIMES[j]]: if (dom[j] >> a) & 1: best = max(best, popcount(mask[(PRIMES[j], a)] & U)) if best == 0: return None cap += best if cap < popcount(U): return None changed = False for i in range(1, NOFF + 1): if (cover >> (i - 1)) & 1: continue c = [j for j in rem if dom[j] & cands[i][j]] if not c: return None if len(c) == 1: j = c[0] nd = dom[j] & cands[i][j] if nd != dom[j]: if nd == 0: return None dom[j] = nd changed = True for j in list(rem): if dom[j] == 0: return None if popcount(dom[j]) == 1: a = dom[j].bit_length() - 1 cover |= mask[(PRIMES[j], a)] assign[PRIMES[j]] = a rem.discard(j) changed = True if not changed: return dom, rem, cover, assign def dfs(dom, rem, cover, assign): nodes[0] += 1 r = propagate(dom, rem, cover, assign) if r is None: return dom, rem, cover, assign = r if not rem: if cover == FULL: solutions.append(dict(assign)) return j = min(rem, key=lambda j: popcount(dom[j])) for a in allow[PRIMES[j]]: if not (dom[j] >> a) & 1: continue nd = dict(dom) nd[j] = 1 << a nrem = set(rem) nrem.discard(j) na = dict(assign) na[PRIMES[j]] = a dfs(nd, nrem, cover | mask[(PRIMES[j], a)], na) dom0 = {j: sum(1 << a for a in allow[PRIMES[j]]) for j in range(len(PRIMES))} dfs(dom0, set(range(len(PRIMES))), 0, {}) def crt(res): n, M = 0, 1 for j, p in enumerate(PRIMES): if p not in res: raise ValueError("incomplete phase vector") a = res[p] n += M * (((a - n) * pow(M % p, -1, p)) % p) M *= p t = ((5 - n) * pow(M % 6, -1, 6)) % 6 return (n + M * t) % PRIMORIAL positions = sorted({crt(s) for s in solutions}) def slot(n, y): for p in ALLP: if p > y: break if n % p == 0 or (n + 2) % p == 0: return False return True rows = [] for n in positions: assert slot(n, X) and slot(n + G, X), "endpoint not a slot" assert all(not slot(n + 6 * i, X) for i in range(1, NOFF + 1)), "interior survivor" inner = [6 * i for i in range(1, NOFF + 1) if slot(n + 6 * i, PREV)] if inner: L, inte, ends = len(inner) + 1, inner[-1] - inner[0], G - (inner[-1] - inner[0]) else: L, inte, ends = 1, 0, G assert L >= 2 or inte == 0 rows.append((n, L, inte, ends)) return dict(X=X, G=G, LEAST=LEAST, NMAX=NMAX, nodes=nodes[0], vectors=len(solutions), positions=positions, rows=rows, PRIMORIAL=PRIMORIAL, PREV=PREV) print("Endpoint-safe fixed-gap CRT gate at every published level with a recorded least position,") print("x = 13..43. The assigned target of job #1026 is 41# and 43#; 13#..37# are the") print("calibration levels: the gate is shown to count right where custody already knows") print("the answer before it is used where custody does not.") print("Published inputs (research/exact-g2-ladder.js LADDER): G2(x#), least position, multiplicity.") print("The gate freezes G and searches phases only; it never scans a period and never") print("searches for a maximum, so maximality is an input, not an output.") print() print(" x G least pos nmax gate pos match nodes phase vecs depth,interior,endsum:count") results = {} for X in sorted(PUB): r = run_level(X) results[X] = r ok = (len(r["positions"]) == r["NMAX"]) and (r["LEAST"] in r["positions"]) c = Counter((a, b, cc) for _, a, b, cc in r["rows"]) split = "; ".join("(%d,%d,%d):%d" % (k[0], k[1], k[2], c[k]) for k in sorted(c)) print("%3d %4d %-16d %-5d %-9d %-7s %-7d %-11d %s" % (X, r["G"], r["LEAST"], r["NMAX"], len(r["positions"]), "YES" if ok else "NO", r["nodes"], r["vectors"], split)) print() r = results[31] print("=== 31# detail: the four published attainers ===") for n, L, inte, ends in r["rows"]: refl = (r["PRIMORIAL"] - 2 - r["G"] - n) % r["PRIMORIAL"] print(" pos %-16d L=%d interior=%d endsum=%d reflection %d%s" % (n, L, inte, ends, refl, " (in set)" if refl in r["positions"] else " (NOT in set)")) known = {r["LEAST"], (r["PRIMORIAL"] - 2 - r["G"] - r["LEAST"]) % r["PRIMORIAL"]} missing = [n for n in r["positions"] if n not in known] print(" least + reflection (published custody pair):", sorted(known)) print(" recovered missing pair:", missing) print(" coverage: %d of published multiplicity %d" % (len(r["positions"]), r["NMAX"])) print() print("Prior claim under test (return #404): 31# witnesses are 2 of 4, a partial subset") print("with anatomy (L=3, interior 60, endsum 288) : 2. Observed here:") c31 = Counter((a, b, cc) for _, a, b, cc in r["rows"]) print(" ", {("L=%d" % k[0], "interior=%d" % k[1], "endsum=%d" % k[2]): v for k, v in sorted(c31.items())}) log("total %.2fs" % (time.time() - T0))