#!/usr/bin/env python3 """Job 2612 / route 100: small-base sweep for drop = D(P,p,A) witnesses (prereg-2612.md). Needs ./kstar (cc -O2 -o kstar kstar.c -lpthread; kstar.c from #1812) in the working directory. Usage: python3 sweep2612.py [threads] stdout: one JSON object; progress to stderr. """ import itertools, json, subprocess, sys from collections import defaultdict from dbound2612 import alive, D, primes_upto TH = sys.argv[1] if len(sys.argv) > 1 else "4" CONF = [(2, [q for q in primes_upto(43) if q >= 3], 2e8), (6, [q for q in primes_upto(47) if q >= 5], 5e8)] MP3, MP2, PMAX, WALL = 2e9, 1e8, 61, 1200 import time T0 = time.time() def kstar(rows): inp = "".join("%d %d %d %s\n" % (P, p, len(R), " ".join(map(str, R))) for P, p, R in rows) res = subprocess.run(["./kstar", TH], input=inp, capture_output=True, text=True, check=True) return [int(l.split()[-1]) for l in res.stdout.splitlines()] def prod(xs): m = 1 for x in xs: m *= x return m out = {"prereg_sha256": open("prereg-2612.sha256").read().split()[0], "bases": {}} for P, pool, mmax in CONF: cls = alive(P); dm = {} sets = [R for n in range(2, len(pool) + 1) for R in itertools.combinations(pool, n) if P * prod(R) <= mmax] A = kstar([(P, 1, R) for R in sets]) brow = [] for R, a in zip(sets, A): if a < 0: continue for p in primes_upto(PMAX): if P % p == 0 or p in R: continue if (p, a) not in dm: dm[(p, a)] = D(P, p, a, cls)[0] mp = P * prod(R) * p if (dm[(p, a)] >= 3 and mp <= MP3) or (dm[(p, a)] == 2 and mp <= MP2): brow.append((P, p, R, a, dm[(p, a)])) brow.sort(key=lambda r: (r[0] * prod(r[2]) * r[1], r)) print("P=%d sets=%d brows=%d" % (P, len(sets), len(brow)), file=sys.stderr) B, done_mp = [], 0 budget = WALL * (1 if P == 6 else 0.5) t1 = time.time() with open("sweep2612.jsonl", "a") as jl: for i in range(0, len(brow), 100): ch = brow[i:i + 100] bb = kstar([(P, p, R) for P, p, R, a, d in ch]) for (P_, p, R, a, d), b in zip(ch, bb): jl.write(json.dumps([P_, p, list(R), a, b, d]) + "\n") jl.flush() B += bb; done_mp = P * prod(ch[-1][2]) * ch[-1][1] if time.time() - t1 > budget: break brow = brow[:len(B)] print("P=%d done %d rows, Mp reached %d" % (P, len(B), done_mp), file=sys.stderr) shapes = defaultdict(lambda: [None, 0, None]) # (p,A,D) -> [max drop, rows, witness] guard, wit3 = [], [] for (P_, p, R, a, d), b in zip(brow, B): drop = a - b s = shapes[(p, a, d)] s[1] += 1 if s[0] is None or drop > s[0]: s[0], s[2] = drop, list(R) if drop > d: guard.append([p, list(R), a, b, d]) if drop == d and d >= 3: wit3.append([p, list(R), a, b, d]) tab = sorted([p, a, d, s[0], s[1], s[2]] for (p, a, d), s in shapes.items()) out["bases"][str(P)] = {"sets": len(sets), "rows_done": len(B), "Mp_reached": done_mp, "A_max": max(A), "b_rows": len(brow), "guard_drop_gt_D": guard, "drop_eq_D_ge3": wit3, "shapes_p_A_D_maxdrop_rows_witnessR": tab, "attained": [t[:4] + [t[5]] for t in tab if t[3] == t[2]]} print(json.dumps(out, separators=(",", ":")))