spb/prime-mystery-engine

1#!/usr/bin/env python32# =============================================================================3# prover_desert2.py — Cycle 1 PROVER (attempt 2): hybrid covering desert4# Author: Simon-Pierre Boucher — contact@spboucher.ai5# =============================================================================6# Upgrade over prover_desert.py: the covering system (primes <= 59) covers MOST7# of positions 1..L; the few uncovered positions are certified composite for8# the specific shift t by an explicit small factor (trial division) or an9# explicit Miller-Rabin witness (a valid compositeness certificate).10# Endpoints N, N+L+1 certified prime by deterministic MR (N+L+1 < 3.317e24).11# Deterministic search; no randomness.12# Output: certs/desert_certificate.json (overwrites attempt 1 - superseded)13# =============================================================================1415import json16import time17from math import log18from pathlib import Path1920from core import is_prime, primes_upto2122CERTS = Path(__file__).resolve().parent.parent / "certs"23MR_LIMIT = 3_317_044_064_679_887_385_961_98124TRIAL_PRIMES = [int(p) for p in primes_upto(1_000_000)]252627def greedy_cover_partial(qs, L):28    """One class per prime, greedy max coverage of 1..L; classes may not touch29    positions 0 or L+1. Returns (classes, uncovered_list)."""30    uncovered = set(range(1, L + 1))31    classes = {}32    for p in sorted(qs):33        best_a, best_hits = None, -134        for a in range(p):35            if a == 0 or a == (L + 1) % p:36                continue37            hits = sum(1 for i in uncovered if i % p == a)38            if hits > best_hits:39                best_a, best_hits = a, hits40        classes[p] = best_a41        uncovered = {i for i in uncovered if i % p != best_a}42    return classes, sorted(uncovered)434445def crt(classes):46    x, mod = 0, 147    for p, a in sorted(classes.items()):48        r = (-a) % p49        k = ((r - x) * pow(mod, -1, p)) % p50        x += mod * k51        mod *= p52    return x, mod535455def mr_witness_for(n):56    """Return a base a proving n composite (strong witness), or None."""57    d, r = n - 1, 058    while d % 2 == 0:59        d //= 260        r += 161    for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):62        x = pow(a, d, n)63        if x == 1 or x == n - 1:64            continue65        for _ in range(r - 1):66            x = x * x % n67            if x == n - 1:68                break69        else:70            return a71    return None727374def small_factor(n):75    for q in TRIAL_PRIMES:76        if q * q > n:77            return None78        if n % q == 0:79            return q80    return None818283def main():84    t0 = time.time()85    m = 5986    qs = [int(p) for p in primes_upto(m)]87    # choose the largest odd L whose greedy covering leaves <= UMAX holes88    for UMAX in (16, 12, 8):89        chosen = None90        for L in range(91, 300, 2):91            classes, unc = greedy_cover_partial(qs, L)92            if len(unc) <= UMAX:93                chosen = (L, classes, unc)94        if chosen is None:95            continue96        L, classes, unc = chosen97        print(f"UMAX={UMAX}: L={L}, holes={len(unc)} at {unc}")98        x, P = crt(classes)99        t_max = (MR_LIMIT - x - L - 1) // P100        hit = None101        for t in range(1, int(t_max) + 1):102            N = x + t * P103            if not is_prime(N):104                continue105            if not is_prime(N + L + 1):106                continue107            if all(not is_prime(N + i) for i in unc):108                hit = (t, N)109                break110        if hit:111            break112        print(f"  no t <= {t_max} works; relaxing")113    assert hit, "hybrid construction failed at all UMAX levels"114    t, N = hit115    gap = L + 1116    print(f"t={t}  N={N} ({len(str(N))} digits)")117    print(f"CERTIFIED GAP {gap}, merit {gap/log(N):.4f}, csg {gap/log(N)**2:.5f} "118          f"[{time.time()-t0:.1f}s]")119120    # build interior certificates121    interior = {}122    for i in range(1, L + 1):123        cov = [p for p, a in classes.items() if i % p == a]124        if cov:125            q = min(cov)126            assert (N + i) % q == 0 and N + i > q127            interior[str(i)] = {"type": "covering_factor", "q": q}128        else:129            f = small_factor(N + i)130            if f:131                interior[str(i)] = {"type": "trial_factor", "q": f}132            else:133                a = mr_witness_for(N + i)134                assert a is not None, f"no witness for position {i}?!"135                interior[str(i)] = {"type": "mr_witness", "a": a}136    n_types = {}137    for v in interior.values():138        n_types[v["type"]] = n_types.get(v["type"], 0) + 1139    print("interior certificate types:", n_types)140141    cert = {142        "title": "Certified prime desert via hybrid covering system",143        "author": "Simon-Pierre Boucher — contact@spboucher.ai",144        "date": "2026-08-06",145        "claim": f"N and N+{gap} are consecutive primes (gap exactly {gap}).",146        "N": str(N),147        "gap": gap,148        "merit": round(gap / log(N), 5),149        "csg_ratio": round(gap / log(N) ** 2, 6),150        "construction": {151            "prime_set_max": m,152            "primorial_P": str(crt(classes)[1]),153            "crt_residue_x": str(x),154            "shift_t": t,155            "classes_a_p": {str(p): a for p, a in sorted(classes.items())},156            "holes": unc,157            "note": "positions with a covering factor are composite for EVERY "158                    "shift t (proven); hole positions are certified composite "159                    "for THIS t by explicit factor or strong MR witness",160        },161        "interior_certificates": interior,162        "endpoint_primality": {163            "method": "deterministic Miller-Rabin, bases {2..37} (12 bases), "164                      "valid for n < 3.317e24 (Sorenson-Webster 2015)",165            "validity_bound": str(MR_LIMIT),166            "both_endpoints_below_bound": bool(N + gap < MR_LIMIT),167        },168        "epistemic_status": "CERTIFIED construction; NOT a record (see records.md: "169                            "merit record 41.94, largest maximal gap 1854). "170                            "Baseline with same primes: classic primorial gives gap 61; "171                            "pure covering (attempt 1) gave gap 90.",172    }173    with open(CERTS / "desert_certificate.json", "w") as f:174        json.dump(cert, f, indent=2)175    print("certificate written:", CERTS / "desert_certificate.json")176177178if __name__ == "__main__":179    main()180