#!/usr/bin/env python3 """Independent checker for job #4434 (route 117 step check). Stdlib only, offline. Claim checked: route 117's step (from #1812) is not answered by the returns on record, and the record does answer part of it -- the step's |R| = 7 cell is empty under its own cap, and #1833's proven phase bound D(30,p,A) removes 1,221 of the 2,028 rows the step's own filter keeps in the population #1812 already measured, and removes *every* row in which a rise of -3 or worse is possible. Self-contained: the enumerator and the exact phase bound below are the same closed forms as .solveathome/private/lib/covering/base_extension.py, inlined so the package needs no library path (a shared component of the author's, declared as such). Reads (all relative to this file's directory): stepcheck_facts.json the step's enumerated population and its price dgate30.json #1833's D table re-indexed for P=30 dgate_saving.json what the D gate removes, and the like-for-like price served/f1833_dbound2612.json return #1833's served table (input) served/f1812_sweep2775b.json return #1812's served sweep (input) Exit 0 and "ALL CHECKS PASS" only when every check passes; exit 1 otherwise. python3 verify_route117_stepcheck.py [--dir .] """ import argparse import hashlib import itertools import json import os import sys HERE = os.path.dirname(os.path.abspath(__file__)) # ---- the author's closed forms, inlined (shared component) ----------------- def primes_upto(n): return [q for q in range(2, n + 1) if all(q % d for d in range(2, int(q ** 0.5) + 1))] def alive_classes(P): fs = [q for q in primes_upto(P) if P % q == 0] return [c for c in range(P) if all(c % q not in (0, (q - 2) % q) for q in fs)] def period_M(P, R): m = P for q in R: m *= q return m def population(P, r_sizes, m_cap, p_max=97, p_min=7): base = [q for q in primes_upto(p_max) if q >= p_min and P % q] out = [] for nr in r_sizes: for R in itertools.combinations(base, nr): M = period_M(P, R) if M <= m_cap: out.append({"nR": nr, "R": R, "M": M, "ps": [p for p in base if p not in R]}) return out def price(pop, rate): sum_M = sum(c["M"] for c in pop) sum_Mp = sum(c["M"] * p for c in pop for p in c["ps"]) return {"rows": sum(len(c["ps"]) for c in pop), "sum_M": sum_M, "sum_Mp": sum_Mp, "cpu_hours": (sum_M + sum_Mp) / float(rate) / 3600.0} def phase_bound_D(P, p, L, classes=None): cls = alive_classes(P) if classes is None else list(classes) m = len(cls) best = None for phi in range(m): o = [((phi + i) // m) * P + cls[(phi + i) % m] - cls[phi] for i in range(L)] cnt = [0] * p for x in o: cnt[x % p] += 1 k = min(cnt[(-s) % p] + cnt[(-s - 2) % p] for s in range(p)) best = k if best is None else max(best, k) return best def min_L_for_drop(P, p, want, L_max=60): cls = alive_classes(P) for L in range(1, L_max + 1): if phase_bound_D(P, p, L, cls) >= want: return L return None P = 30 CAP_OLD, CAP_STEP = 3 * 10 ** 8, 3 * 10 ** 9 RATE_1384 = 4.17e8 FAILS = [] NCHECK = [0] def chk(name, got, want, tol=None): NCHECK[0] += 1 ok = (abs(got - want) <= tol) if tol is not None else (got == want) if not ok: FAILS.append("%s: got %r want %r" % (name, got, want)) print("%-58s %-32s %s" % (name, repr(got)[:32], "PASS" if ok else "FAIL")) def sha256_file(path, crlf_normalise=False): b = open(path, "rb").read() if crlf_normalise: b = b.replace(b"\r\n", b"\n") return hashlib.sha256(b).hexdigest() def main(): ap = argparse.ArgumentParser() ap.add_argument("--dir", default=HERE) a = ap.parse_args() d = a.dir facts = json.load(open(os.path.join(d, "stepcheck_facts.json"), encoding="utf-8")) gate = json.load(open(os.path.join(d, "dgate30.json"), encoding="utf-8")) save = json.load(open(os.path.join(d, "dgate_saving.json"), encoding="utf-8")) served_d = os.path.join(d, "served", "f1833_dbound2612.json") served_1812 = os.path.join(d, "served", "f1812_sweep2775b.json") db = json.load(open(served_d, encoding="utf-8")) sw = json.load(open(served_1812, encoding="utf-8")) print("== inputs") print(" #1833 dbound2612.json sha256(LF) %s" % sha256_file(served_d, True)[:32]) print(" #1812 sweep2775b.json sha256(LF) %s" % sha256_file(served_1812, True)[:32]) # ---- A. the served D table re-indexed, against an independent exact D ---- print("\n== A. #1833's D table, re-indexed vs exact evaluation") strict = {(q, p, L): dd for (q, p, L, fl, dd, dmin) in db["strict"]} def D(p, L): fl = (2 * L) // p if fl == 0: return 0 return strict.get((P, p, L), fl) agree = 0 total = 0 for p in (7, 11, 13, 17, 19, 23, 29): for L in range(1, 41): if (2 * L) // p == 0: continue total += 1 if phase_bound_D(P, p, L) == D(p, L): agree += 1 chk("A1 re-index agrees with exact D on all shapes", agree, total) chk("A2 shapes compared (>=200)", total >= 200, True) chk("A3 D <= floor(2L/p) on the whole served table", all(dd <= fl for (q, p, L, fl, dd, dmin) in db["strict"]), True) chk("A4 #1833 prose: D(30,7,L)=0 for L<=7", [phase_bound_D(P, 7, L) for L in (4, 5, 6, 7)], [0, 0, 0, 0]) chk("A5 #1833 prose: D(30,11,17)=D(30,11,18)=D(30,13,20)=2", [phase_bound_D(P, p, L) for (p, L) in ((11, 17), (11, 18), (13, 20))], [2, 2, 2]) chk("A6 #1833 prose: first L with D>=3 is 14,19,21,27,33", [min_L_for_drop(P, p, 3) for p in (7, 11, 13, 17, 19)], [14, 19, 21, 27, 33]) # ---- B. the gate thresholds published in dgate30.json ------------------- print("\n== B. published D gate for P=30") thr = gate["thresholds"] for p, want2, want3 in ((7, 11, 14), (11, 12, 19), (13, 14, 21), (17, 18, 27), (19, 22, 33), (23, 39, 48)): chk("B1 min A with D(30,%d,A)>=2" % p, thr[str(p)]["min_A_drop2_permitted"], want2) chk("B1 min A with D(30,%d,A)>=3" % p, thr[str(p)]["min_A_drop3_permitted"], want3) chk("B2 dgate30 cross-check shape count", gate["cross_check_shapes"], 72) chk("B3 dgate30 declares all cross-checks agree", gate["cross_check_all_agree"], True) # ---- C. what the gate removes from #1812's served rows ----------------- print("\n== C. the gate applied to #1812's served P=30 rows") rows = sw["rows"] stepf = [r for r in rows if r["p"] <= r["A"]] g2 = [r for r in stepf if D(r["p"], r["A"]) >= 2] g3 = [r for r in stepf if D(r["p"], r["A"]) >= 3] chk("C1 served rows", len(rows), 14008) chk("C2 step filter p<=A keeps", len(stepf), 2028) chk("C3 D>=2 keeps", len(g2), 807) chk("C4 D>=3 keeps (none: -3 impossible in scope)", len(g3), 0) chk("C5 D>=2 keeps fraction", round(len(g2) / float(len(stepf)), 6), 0.397929, tol=5e-6) chk("C6 served rows with floor(2A/p)>=3", sum(1 for r in rows if (2 * r["A"]) // r["p"] >= 3), 0) chk("C7 published gate_D_ge_2_kept", save["gate_D_ge_2_kept"], 807) chk("C8 published gate_D_ge_3_kept", save["gate_D_ge_3_kept"], 0) chk("C9 published step_filter_kept", save["step_filter_kept"], 2028) chk("C10 kept-by-p table", save["kept_by_p"], {"7": [694, 0], "11": [814, 621], "13": [520, 186]}) chk("C11 every A>=17 row on record has p>=23 and floor(2A/p)=1", sorted({(r["nR"], r["p"], (2 * r["A"]) // r["p"]) for r in rows if r["A"] >= 17}), [(6, 23, 1), (6, 29, 1), (6, 31, 1), (6, 37, 1)]) # ---- D. the step's population and its price ---------------------------- print("\n== D. the step's own population (P=30, |R| in {5,6,7}, M <= 3e9)") sc = facts["step_population"] old = population(P, (3, 4, 5, 6), CAP_OLD) pop = population(P, (5, 6, 7), CAP_STEP) by = {} for c in pop: by[c["nR"]] = by.get(c["nR"], 0) + 1 chk("D1 enumerator reproduces #1812's 9,965 R-sets at M<=3e8", len(old), 9965) chk("D2 all served R-sets inside the reproduction", len({tuple(r["R"]) for r in rows} - {c["R"] for c in old}), 0) chk("D3 R_sets by size", {str(k): v for k, v in sorted(by.items())}, {"5": 13890, "6": 1059}) chk("D4 |R|=7 cell empty", population(P, (7,), CAP_STEP), []) chk("D5 min M over |R|=7", period_M(P, (7, 11, 13, 17, 19, 23, 29)), 6469693230) chk("D6 published R7_min_M", sc["R7_min_M"], 6469693230) chk("D7 new R-sets over M=3e8", len([c for c in pop if c["M"] > CAP_OLD]), 12854) chk("D8 published R_sets_new", sc["R_sets_new_over_M3e8"], 12854) pr = price(pop, RATE_1384) chk("D9 rows in the population", pr["rows"], 253074) chk("D10 sum_M", pr["sum_M"], 18468275337630) chk("D11 sum_Mp", pr["sum_Mp"], 15474105210719940) chk("D12 published sum_Mp", sc["sum_Mp_all"], 15474105210719940) chk("D13 price at #1384's rate (CPU-h)", round(pr["cpu_hours"], 3), 10320.126, tol=5e-3) chk("D14 published price matches", round(facts["price"]["cpu_hours_all"], 3), 10320.126, tol=5e-3) # ---- E. like-for-like price against #1812's own wall clock ------------- print("\n== E. like-for-like price") work_1812 = sum(c["M"] for c in old) + sw["price"]["sum_Mp"] work_step = pr["sum_M"] + pr["sum_Mp"] ratio = work_step / float(work_1812) chk("E1 work ratio step/#1812 addendum", round(ratio, 1), 750.2, tol=0.05) chk("E2 published ratio", round(save["price"]["ratio"], 1), 750.2, tol=0.05) chk("E3 like-for-like CPU-h (983 s wall, 6 threads)", round(ratio * 983.0 * 6 / 3600.0, 1), 1229.1, tol=0.2) chk("E4 published like-for-like CPU-h", round(save["price"]["cpu_hours_step_like_for_like"], 1), 1229.1, tol=0.2) chk("E5 a 2 CPU-h run covers a fraction of the population", save["price"]["fraction_of_population_covered_by_budget"] < 0.01, True) # ---- F. the served sweep's own summary fields -------------------------- print("\n== F. #1812's served summary (the population the step extends)") chk("F1 served rows", sw["rows"].__len__(), 14008) chk("F2 served min_rise", sw["min_rise"], -1) chk("F3 served H1b (no rise <= -2)", sw["H1b_no_rise_le_minus_2"], True) chk("F4 served H2b (no rise <= -3)", sw["H2b_no_rise_le_minus_3"], True) chk("F5 served max_Mp_reached", sw["max_Mp_reached"], 10407767370) chk("F6 published served max_Mp_reached", facts["served_validation"]["served_max_Mp_reached"], 10407767370) chk("F7 served drops all size 1", sorted({r["rise"] for r in sw["drops"]}), [-1]) chk("F8 A histogram at |R|=6", sw["A_hist"]["6"], {"19": 1, "20": 1}) print("\n%d checks, %d FAIL" % (NCHECK[0], len(FAILS))) for f in FAILS: print(" FAIL", f) if FAILS: return 1 print("ALL CHECKS PASS") return 0 if __name__ == "__main__": sys.exit(main())