"""h5_verify.py -- reconstruction and double verification of the admissible 232 465 000-tuple giving H_5 <= 4 817 211 684 with the certificates of hexagon:2610.00419v2. Input: the certificate bundle of hexagon:2610.00419v2 (prime_gap_verified_certificates.zip, unpacked; only its data files are read, none of its code is run) and the files of this directory: h5_patches_1.csv, h5_patches_2.csv : prime p, missing residue r_p (replacing the residue of the bundle; r_p != 0 for a pair +-p that is put back, or a moved class) h5_removed.csv : signed elements removed from the parent h5_window.json : the selected window. Steps: 1. residues r_p for 10^7 < p <= 234 360 000 from the bundle (with its three patch files; sha256 of Section 12.3 checked), then the patches above; 2. the tuple: +-1 and +-q, q prime, 10^7 < q, minus the pairs +-p with r_p = 0, minus the removed elements, restricted to [first, last] of h5_window.json; its cardinality must be K; 3. every prime p whose residue is 1 or p-1 (these classes contain +1 or -1) receives the smallest class c >= 2 that contains no element of the tuple (program C1 below); 4. verifier A (numpy): every prime p <= K has an empty class (p <= 10^7: class 0; otherwise r_p, along the whole progression on both sides); count of the pairs further apart than D; also for D - 1; 5. verifier B (independent C program, its own byte-bit sieve): the same checks. Memory: about 5 GB. Time: about 10 minutes. usage: python3 h5_verify.py [bundle root] (default ARGS below)""" import sys, os, gzip, csv, json, hashlib, subprocess, tempfile, time import numpy as np ARGS = ['prime_gap_verified/prime_gap_boundary_bundle'] HERE = os.path.dirname(os.path.abspath(__file__)) t0 = time.time() def log(s): print(f"[{time.time()-t0:6.0f}s] {s}", flush=True) CUT, UP, L, K = 10_000_000, 234_360_000, 2_432_107_459, 232_465_000 C1 = r""" #include #include #include #include typedef uint8_t u8; #define GB(a,x) ((a[(x)>>3]>>((x)&7))&1) #define SB(a,x) (a[(x)>>3]|=(u8)(1<<((x)&7))) #define CB(a,x) (a[(x)>>3]&=(u8)~(1<<((x)&7))) /* usage: c1 cp.u32 res.u32 removed.txt A B out.u32 : moves the classes 1 and p-1 to the smallest empty class c >= 2 */ int main(int argc, char **argv){ long long A = atoll(argv[4]), B = atoll(argv[5]), M = (A > B ? A : B) + 1; u8 *comp = calloc(M / 8 + 2, 1); SB(comp, 0); SB(comp, 1); for (long long i = 2; i * i <= M; i++) if (!GB(comp, i)) for (long long j = i * i; j <= M; j += i) SB(comp, j); FILE *f = fopen(argv[1], "rb"); fseek(f, 0, SEEK_END); long n = ftell(f) / 4; rewind(f); uint32_t *cp = malloc(4 * n), *res = malloc(4 * n); if (fread(cp, 4, n, f) != (size_t)n) return 3; fclose(f); f = fopen(argv[2], "rb"); if (fread(res, 4, n, f) != (size_t)n) return 3; fclose(f); u8 *pos = calloc(M / 8 + 2, 1), *neg = calloc(M / 8 + 2, 1); for (long long x = 10000001; x <= M; x++) if (!GB(comp, x)) { if (x <= B) SB(pos, x); if (x <= A) SB(neg, x); } SB(pos, 1); SB(neg, 1); for (long i = 0; i < n; i++) if (res[i] == 0 && cp[i] <= M) { CB(pos, cp[i]); CB(neg, cp[i]); } f = fopen(argv[3], "r"); long long x; while (fscanf(f, "%lld", &x) == 1) { if (x > 0 && x <= B) CB(pos, x); if (x < 0 && -x <= A) CB(neg, -x); } fclose(f); long moved = 0, fail = 0; for (long i = 0; i < n; i++) { long long p = cp[i]; if (!(res[i] == 1 || res[i] == p - 1)) continue; long long found = -1; for (long long c = 2; c <= p - 2 && found < 0; c++) { int hit = 0; for (long long y = c; y <= B && !hit; y += p) if (GB(pos, y)) hit = 1; for (long long y = p - c; y <= A && !hit; y += p) if (GB(neg, y)) hit = 1; if (!hit) found = c; } if (found < 0) fail++; else { res[i] = (uint32_t)found; moved++; } } printf("classes 1 and p-1 moved: %ld, failures: %ld\n", moved, fail); f = fopen(argv[6], "wb"); fwrite(res, 4, n, f); fclose(f); return fail != 0; } """ def build(root, tmp): odd = np.ones((UP + 1) // 2, dtype=bool); odd[0] = False i = 1 while (2 * i + 1) ** 2 <= UP: if odd[i]: p = 2 * i + 1; odd[(p * p) // 2::p] = False i += 1 cp = 2 * np.flatnonzero(odd) + 1; cp = cp[cp > CUT].astype(np.int64) res = np.frombuffer(gzip.decompress(open(f"{root}/baseline/inherited/tuples/h5_residues.u32.gz", "rb").read()), dtype="> 1] = False pos = odd; neg = odd.copy() for x in open(os.path.join(tmp, "removed.txt")): x = int(x) if x > 0 and x <= B: assert pos[x >> 1]; pos[x >> 1] = False if x < 0 and -x <= A: assert neg[-x >> 1]; neg[-x >> 1] = False pos[0] = True; neg[0] = True pos[(B >> 1) + 1:] = False; neg[(A >> 1) + 1:] = False npos, nneg = int(pos.sum()), int(neg.sum()) assert pos[B >> 1] and neg[A >> 1] log(f"A: tuple in [-{A}, {B}]: {nneg} negative and {npos} positive entries, total {nneg + npos} (K = {K})") assert nneg + npos == K and nneg == W["negative_entries"] fails = 0; nz = np.flatnonzero(res != 0) for a in range(0, len(nz), 20000): idx = nz[a:a + 20000]; p = cp[idx]; r = res[idx] J = np.arange(M // int(p[0]) + 2, dtype=np.int64) for t, arr, lim in ((r, pos, B), (p - r, neg, A)): q = t[:, None] + p[:, None] * J[None, :] ok = (q <= lim) & (q & 1 == 1) fails += int(arr[q[ok] >> 1].sum()) zp = cp[res == 0]; zp = zp[zp <= M]; fails0 = int(pos[zp >> 1].sum() + neg[zp >> 1].sum()) # primes p <= 10^7: the entries are +-1 and +-q with q prime > 10^7 (sieve above), so class 0 is empty qp = (2 * np.flatnonzero(pos) + 1).astype(np.int64); qn = (2 * np.flatnonzero(neg) + 1).astype(np.int64) def lp(Dv): aa = qn[int(np.searchsorted(qn, Dv - qp[-1], side="right")):] return int(np.sum(len(qp) - np.searchsorted(qp, Dv - aa, side="right"), dtype=np.int64)) l0, l1 = lp(D), lp(D - 1) log(f"A: nonzero classes {len(nz)}, failures {fails}; pairs +-p with r_p = 0 present: {fails0}") log(f"A: pairs further apart than {D}: {l0} (budget {budget}); further apart than {D - 1}: {l1}") return fails == 0 and fails0 == 0 and l0 <= budget and l0 == W["pairs_further_apart_than_D"] def main(): root = (sys.argv[1:] or ARGS)[0] W = json.load(open(os.path.join(HERE, "h5_window.json"))) tmp = tempfile.mkdtemp() nrm = build(root, tmp); log(f"removed elements: {nrm}") open(os.path.join(tmp, "c1.c"), "w").write(C1) subprocess.run(["gcc", "-O2", "-o", os.path.join(tmp, "c1"), os.path.join(tmp, "c1.c")], check=True) out = subprocess.run([os.path.join(tmp, "c1"), os.path.join(tmp, "cp.u32"), os.path.join(tmp, "res.u32"), os.path.join(tmp, "removed.txt"), str(-W["first"]), str(W["last"]), os.path.join(tmp, "res_final.u32")], capture_output=True, text=True) log("C1: " + out.stdout.strip()); assert out.returncode == 0 okA = verifier_A(tmp, W) log(f"verifier A: {'ADMISSIBLE, WITHIN THE BUDGET' if okA else 'FAILURE'}") sys.path.insert(0, HERE); from h5_verifier_B import SOURCE as src open(os.path.join(tmp, "vb.c"), "w").write(src) subprocess.run(["gcc", "-O2", "-o", os.path.join(tmp, "vb"), os.path.join(tmp, "vb.c")], check=True) out = subprocess.run([os.path.join(tmp, "vb"), os.path.join(tmp, "cp.u32"), os.path.join(tmp, "res_final.u32"), os.path.join(tmp, "removed.txt"), "1", str(-W["first"]), str(W["last"]), str(W["D"]), str(W["pair_budget"])], capture_output=True, text=True) for line in out.stdout.strip().splitlines(): log("B: " + line) okB = out.returncode == 0 log(f"RESULT: H_5 <= {W['D']} (with the certificates of hexagon:2610.00419v2): {'CONFIRMED by A and B' if okA and okB else 'NOT CONFIRMED'}") try: input("Press Enter...") except EOFError: pass if __name__ == "__main__": main()