#!/usr/bin/env python3 """Route 64 / job #1813: the positive branch of the L=30 covering search at s=37. The route's method names kstar_rework.c. That file is not in the record -- see the return. This is a port of the one engine that IS in the record: boundary_search30.rs from return #938 (sha256 c43106559b2f...), reimplemented line-for-line in Python because this machine has no rustc and no C compiler. The port is validated by CONTROL, not by assertion: run with --windows 2000000 --offset 0 and it must reproduce #938's search30.json exactly -- capacity_negative 1584728, searched 415272, node_limited 0, covered 0, nodes 24521166, and the full capacity histogram. If any of those differs the port is wrong and nothing else it prints means anything. Object: xs = natal survivors at s=37, i.e. r = 6i+5 with p does not divide r and p does not divide r+2 for every p <= 37. A window is L=30 consecutive survivors. Scour primes Q = 41..73. Slot i is killed by prime q at phase a iff xs[i] = a or a-2 (mod q). A cover is one phase per prime killing all 30 slots. stdout is the artifact; progress and timing go to stderr. """ import argparse, json, sys, time Q = [41, 43, 47, 53, 59, 61, 67, 71, 73] L = 30 STOP = 100_000 # node cap per window, as in the Rust NQ = len(Q) def natal_survivors(n_limit): """r = 6i+5 surviving p <= 37 on both r and r+2, exactly as the Rust sieves it.""" sieve = bytearray(b'\x01') * n_limit for p in (5, 7, 11, 13, 17, 19, 23, 29, 31, 37): inv = next(j for j in range(1, p) if 6 * j % p == 1) for b in (5, 7): first = ((p - b % p) * inv) % p sieve[first::p] = bytearray(len(range(first, n_limit, p))) return [6 * i + 5 for i in range(n_limit) if sieve[i]] def dfs(todo, used, masks, residues, counter): counter[0] += 1 if counter[0] > STOP: raise OverflowError if todo == 0: return True cap = 0 for k in range(NQ): if not (used >> k) & 1: mk = masks[k] cap += max(bin(mk[a] & todo).count('1') for a in range(Q[k])) if cap < bin(todo).count('1'): return False i = (todo & -todo).bit_length() - 1 for k in range(NQ): if not (used >> k) & 1: r = residues[i][k] for a in (r, (r + 2) % Q[k]): if dfs(todo & ~masks[k][a], used | (1 << k), masks, residues, counter): ANSWER[k] = a return True return False ANSWER = [0] * NQ def main(): ap = argparse.ArgumentParser() ap.add_argument('--windows', type=int, default=2_000_000) ap.add_argument('--offset', type=int, default=0, help='skip this many survivors first') ap.add_argument('--limit', type=int, default=12_000_000, help='sieve bound in i') a = ap.parse_args() t0 = time.process_time() xs = natal_survivors(a.limit) print(json.dumps({'stage': 'sieved', 'survivors': len(xs), 'cpu': round(time.process_time() - t0, 2)}), file=sys.stderr, flush=True) need = a.offset + a.windows + L if len(xs) < need: print(json.dumps({'error': 'not enough survivors', 'have': len(xs), 'need': need})) return 1 # rolling counts per prime, with the histogram trick so max is O(1) amortised counts = [[0] * 73 for _ in range(NQ)] hist = [[0] * 40 for _ in range(NQ)] mx = [0] * NQ off = a.offset for k in range(NQ): q = Q[k] ck = counts[k] for x in xs[off:off + L]: r = x % q ck[r] += 1 ck[(r + 2) % q] += 1 hk = hist[k] for v in ck[:q]: hk[v] += 1 mx[k] = max(ck[:q]) def change(k, aa, inc): ck, hk = counts[k], hist[k] old = ck[aa] hk[old] -= 1 new = old + 1 if inc else old - 1 ck[aa] = new hk[new] += 1 if new > mx[k]: mx[k] = new while hk[mx[k]] == 0: mx[k] -= 1 filtered = searched = limited = covered = 0 nodes_total = 0 caphist = {} first_cover = None witness = None t1 = time.process_time() for j in range(a.windows): if j > 0: jj = off + j for k in range(NQ): q = Q[k] aa = xs[jj - 1] % q bb = xs[jj + L - 1] % q change(k, aa, False) change(k, (aa + 2) % q, False) change(k, bb, True) change(k, (bb + 2) % q, True) cap = 0 for k in range(NQ): cap += mx[k] caphist[cap] = caphist.get(cap, 0) + 1 if cap < L: filtered += 1 continue searched += 1 base = off + j masks = [[0] * 73 for _ in range(NQ)] residues = [[0] * NQ for _ in range(L)] for i in range(L): x = xs[base + i] for k in range(NQ): q = Q[k] r = x % q residues[i][k] = r masks[k][r] |= 1 << i masks[k][(r + 2) % q] |= 1 << i counter = [0] try: ok = dfs((1 << L) - 1, 0, masks, residues, counter) except OverflowError: limited += 1 ok = False nodes_total += counter[0] if ok: covered += 1 if first_cover is None: first_cover = xs[base] witness = {'slots': xs[base:base + L], 'phases': {str(Q[k]): ANSWER[k] for k in range(NQ)}} print(json.dumps({'stage': 'COVER FOUND', 'start': first_cover}), file=sys.stderr, flush=True) if (j + 1) % 200000 == 0: print(json.dumps({'stage': 'progress', 'windows': j + 1, 'searched': searched, 'covered': covered, 'cpu': round(time.process_time() - t1, 1)}), file=sys.stderr, flush=True) out = {'L': L, 'offset': a.offset, 'windows': a.windows, 'first_start': xs[off], 'last_start': xs[off + a.windows - 1], 'last_end': xs[off + a.windows + L - 2], 'capacity_negative': filtered, 'searched': searched, 'node_limited': limited, 'covered': covered, 'first_cover': first_cover, 'nodes': nodes_total, 'capacity_histogram': {str(k): caphist[k] for k in sorted(caphist)}, 'witness': witness} print(json.dumps(out, indent=1)) print(json.dumps({'stage': 'complete', 'cpu': round(time.process_time() - t0, 1)}), file=sys.stderr) return 0 if __name__ == '__main__': raise SystemExit(main())