#!/usr/bin/env python3 """Job #1080 (route 16 pursuit) -- the fold's qualifying-gap supply in closed form. Claim checked here (proof in the report): at fold x, with G0 / G2 the number of cyclic gaps of one period of T_(x-1) that are = 0 / = +-2 (mod x), the whole-phase counts of return #442 are X = G2 + 2*G0, Z = 2*G0, Q = 2*G2, F = (x-2)*G0 + (x-3)*G2, Nq = x*(G0 + G2) = x*(X - Z/2), so Q = 2*(X - Z) is an identity. Per rotation k (split.py's convention: the pairs of period copy k, slot residues rho + k*M mod x, M = (x-1)#), the residual is a step-2 second difference: Q_k - 2*(X_k - Z_k) = H(t+2) + H(t-2) - 2*H(t), t = -k*M mod x, where H(t) counts the +-2-class gaps whose two ends sit at residues {t-2, t} (H(t) = h_-2(t) + h_2(t-2), h_c(rho) = number of gaps = c with left end = rho). Summing over k gives 0 for every x. Everything below is counted two ways: from (G0, G2, H) of one period, and by a direct walk over all x rotations with the dead flags (residue 0 or -2 mod x), as in split.py. Stdout is deterministic JSON. Usage: python supply1080.py [folds...] (default 17 19 23 29). Needs numpy; fold 29 needs ~2 GB. """ import json import sys import numpy as np PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] def tile(x): M = 1 for p in PRIMES: if p < x: M *= p alive = np.ones(M, dtype=bool) for p in (q for q in PRIMES if q < x): alive[0::p] = False alive[(p - 2) % p::p] = False idx = np.flatnonzero(alive).astype(np.int64) del alive gaps = np.concatenate([np.diff(idx), [idx[0] + M - idx[-1]]]) return M, idx, gaps def fold(x): M, idx, gaps = tile(x) N = len(idx) rho = idx % x gm = gaps % x G0 = int((gm == 0).sum()) G2 = int(((gm == 2) | (gm == x - 2)).sum()) # H(t): +-2-class gaps whose ends sit at residues {t-2, t} H = (np.bincount(rho[gm == x - 2], minlength=x) + np.roll(np.bincount(rho[gm == 2], minlength=x), 2)).astype(np.int64) pred = dict(X=G2 + 2 * G0, Z=2 * G0, Q=2 * G2, F=(x - 2) * G0 + (x - 3) * G2, Nq=x * (G0 + G2), class0=x * G0, inner_not_qualifying=0) qual = (gm == 0) | (gm == 2) | (gm == x - 2) tot = dict(X=0, Z=0, Q=0, F=0, Nq=0, class0=0, inner_not_qualifying=0) per = [] Mx = M % x for k in range(x): r = (rho + k * Mx) % x dead = (r == 0) | (r == x - 2) dn = np.roll(dead, -1) # right end of pair i is slot i+1 (wrap = first slot of copy k+1) # the wrap pair's right end lies in copy k+1: its residue is rho[0] + (k+1)*M dn[-1] = ((rho[0] + (k + 1) * Mx) % x) in (0, x - 2) both, one, free = dead & dn, dead ^ dn, ~dead & ~dn Xk = int(both.sum()); Zk = int((both & (gm == 0)).sum()) Qk = int((one & qual).sum()); Fk = int((free & qual).sum()) tot["X"] += Xk; tot["Z"] += Zk; tot["Q"] += Qk; tot["F"] += Fk tot["Nq"] += int((both & qual).sum()) + Qk + Fk tot["class0"] += int(((both | one | free) & qual & (gm == 0)).sum()) tot["inner_not_qualifying"] += int((both & ~qual).sum()) t = (-k * Mx) % x lap = int(H[(t + 2) % x] + H[(t - 2) % x] - 2 * H[t]) per.append(dict(k=k, residual=Qk - 2 * (Xk - Zk), laplacian=lap)) return dict(fold=x, old_slots_per_period=N, G0=G0, G2=G2, predicted=pred, direct=tot, closed_form_matches=pred == tot, per_rotation_residuals=[p["residual"] for p in per], laplacian_matches=all(p["residual"] == p["laplacian"] for p in per), H=[int(v) for v in H]) def main(): folds = [int(a) for a in sys.argv[1:]] or [17, 19, 23, 29] out = [] for x in folds: sys.stderr.write("fold %d ...\n" % x) out.append(fold(x)) print(json.dumps(out, indent=1)) if __name__ == "__main__": main()