#!/usr/bin/env python3 """Route 64 / job #1813: how close does the L=30 cover get? The record answers only a decision question -- boundary_search30.rs (#938) reports covered=0 over 2,000,000 windows, and the route asks whether a stronger positive exists. A boolean negative does not say whether 30 is one slot out of reach or ten. This computes the EXACT MAXIMUM number of the 30 slots that any one-phase-per-prime assignment can kill, for every window the capacity filter admits, and reports the distribution. Same object and same sieve as search30.py (ported from boundary_search30.rs): natal survivors at s=37, scour primes 41..73, slot i killed by prime q at phase a iff xs[i] = a or a-2 (mod q). Branch and bound: primes in a fixed order, state = set of slots still uncovered; the bound is covered_so_far + sum over unused primes of their best individual kill on the remaining set -- the same admissible bound the decision version uses as its capacity filter. Prune when the bound cannot beat the best found so far. 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 NQ = len(Q) FULL = (1 << L) - 1 pc = bin def natal_survivors(n_limit): 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 max_cover(masks, best_needed): """Exact maximum number of slots killable, one phase per prime. Returns (best, assignment).""" best = [0] bestasg = [None] # per prime, the distinct useful masks (dedup identical coverage patterns) opts = [] for k in range(NQ): seen = {} for a in range(Q[k]): m = masks[k][a] if m and m not in seen: seen[m] = a opts.append(sorted(seen.items(), key=lambda t: -bin(t[0]).count('1'))) def bound(k, cov): b = bin(cov).count('1') rem = FULL & ~cov for kk in range(k, NQ): best_kk = 0 for m, _ in opts[kk]: c = bin(m & rem).count('1') if c > best_kk: best_kk = c b += best_kk return b def rec(k, cov, asg): if k == NQ: c = bin(cov).count('1') if c > best[0]: best[0] = c bestasg[0] = list(asg) return if bound(k, cov) <= best[0]: return for m, a in opts[k]: asg.append(a) rec(k + 1, cov | m, asg) asg.pop() if best[0] >= best_needed: return rec(0, 0, []) return best[0], bestasg[0] def main(): ap = argparse.ArgumentParser() ap.add_argument('--windows', type=int, default=300_000) ap.add_argument('--limit', type=int, default=4_000_000) ap.add_argument('--min-cap', type=int, default=L, help='only analyse windows with capacity >= this') a = ap.parse_args() t0 = time.process_time() xs = natal_survivors(a.limit) print(json.dumps({'stage': 'sieved', 'survivors': len(xs)}), file=sys.stderr, flush=True) if len(xs) < a.windows + L: print(json.dumps({'error': 'not enough survivors', 'have': len(xs)})) return 1 counts = [[0] * 73 for _ in range(NQ)] hist = [[0] * 40 for _ in range(NQ)] mx = [0] * NQ for k in range(NQ): q = Q[k] ck = counts[k] for x in xs[:L]: r = x % q ck[r] += 1 ck[(r + 2) % q] += 1 for v in ck[:q]: hist[k][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 covhist = {} analysed = 0 best_global = 0 best_window = None for j in range(a.windows): if j > 0: for k in range(NQ): q = Q[k] aa = xs[j - 1] % q bb = xs[j + L - 1] % q change(k, aa, False) change(k, (aa + 2) % q, False) change(k, bb, True) change(k, (bb + 2) % q, True) cap = sum(mx) if cap < a.min_cap: continue analysed += 1 masks = [[0] * 73 for _ in range(NQ)] for i in range(L): x = xs[j + i] for k in range(NQ): q = Q[k] r = x % q masks[k][r] |= 1 << i masks[k][(r + 2) % q] |= 1 << i b, asg = max_cover(masks, L) covhist[b] = covhist.get(b, 0) + 1 if b > best_global: best_global = b best_window = {'start': xs[j], 'capacity': cap, 'max_cover': b, 'phases': {str(Q[k]): asg[k] for k in range(NQ)} if asg else None} print(json.dumps({'stage': 'new best', 'max_cover': b, 'start': xs[j], 'cap': cap}), file=sys.stderr, flush=True) if analysed % 20000 == 0: print(json.dumps({'stage': 'progress', 'windows': j + 1, 'analysed': analysed, 'best': best_global, 'cpu': round(time.process_time() - t0, 1)}), file=sys.stderr, flush=True) out = {'L': L, 'windows': a.windows, 'min_capacity': a.min_cap, 'first_start': xs[0], 'last_start': xs[a.windows - 1], 'analysed': analysed, 'best_max_cover': best_global, 'slots_short_of_L': L - best_global, 'max_cover_histogram': {str(k): covhist[k] for k in sorted(covhist)}, 'best_window': best_window} 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())