spb/prime-mystery-engine
Public
Python 64.3%
TeX 35.7%
1#!/usr/bin/env python32# =============================================================================3# prover_desert.py — Cycle 1 PROVER: certified prime desert via covering system4# Author: Simon-Pierre Boucher — contact@spboucher.ai5# =============================================================================6# Construction:7# 1. Prime set Q = primes <= m. Greedily pick a residue class a_p mod p for8# each p in Q so that every position i in 1..L satisfies i = a_p (mod p)9# for some p, while NO class contains position 0 or L+1.10# 2. CRT: x = -a_p (mod p) for all p. Then for EVERY t >= 0,11# N = x + t*P (P = prod Q) has N+i = 0 (mod q_i) with N+i > q_i,12# hence N+1 .. N+L are ALL composite. <-- PROVEN by covering13# 3. Search the smallest t with N and N+L+1 both prime (deterministic14# Miller-Rabin, valid since N + L + 1 < 3.317e24). Then the gap after N15# is EXACTLY L+1. <-- CERTIFIED16# Baseline to beat: the classic primorial construction with the same Q gives17# only L = (next prime after m) - 1 - 1 interior composites (gap ~ next prime).18# Output: certs/desert_certificate.json (+ console report)19# Deterministic: greedy tie-break is lexicographic; t-search is sequential.20# =============================================================================2122import json23import time24from math import log, prod25from pathlib import Path2627from core import is_prime, primes_upto2829CERTS = Path(__file__).resolve().parent.parent / "certs"30CERTS.mkdir(exist_ok=True)3132MR_LIMIT = 3_317_044_064_679_887_385_961_981333435def greedy_cover(qs, L, order):36 """Try to cover positions 1..L with one class per prime (order given).37 Classes containing position 0 or L+1 are forbidden. Returns {p: a_p} or None."""38 uncovered = set(range(1, L + 1))39 classes = {}40 for p in order:41 best_class, best_hits = None, -142 for a in range(p):43 if a == 0 % p or a == (L + 1) % p:44 continue45 hits = sum(1 for i in uncovered if i % p == a)46 if hits > best_hits:47 best_class, best_hits = a, hits48 if best_class is None:49 return None50 classes[p] = best_class51 uncovered = {i for i in uncovered if i % p != best_class}52 return classes if not uncovered else None535455def max_cover(qs):56 """Largest L (with its classes) coverable by greedy, over a few orderings."""57 best = (0, None)58 orders = [sorted(qs), sorted(qs, reverse=True)]59 for order in orders:60 L = 161 last_good = None62 # increase L until greedy fails twice in a row (L must keep parity odd)63 fails = 064 while fails < 6:65 cand = greedy_cover(qs, L, order)66 if cand:67 last_good = (L, cand)68 fails = 069 else:70 fails += 171 L += 2 # keep L odd: p=2 then covers odds, sparing 0 and L+172 if last_good and last_good[0] > best[0]:73 best = last_good74 return best757677def crt(classes):78 """x with x = -a_p (mod p) for all p; 0 <= x < prod(p)."""79 x, mod = 0, 180 for p, a in sorted(classes.items()):81 r = (-a) % p82 # solve x + mod*k = r (mod p)83 k = ((r - x) * pow(mod, -1, p)) % p84 x += mod * k85 mod *= p86 return x, mod878889def main():90 t0 = time.time()91 m = 5992 qs = [int(p) for p in primes_upto(m)]93 L, classes = max_cover(qs)94 assert classes is not None, "no covering found"95 print(f"prime set: primes <= {m} ({len(qs)} primes); covered interval length L = {L}")96 baseline = int(primes_upto(200)[len(qs)]) - 1 # next prime after m, minus 197 print(f"baseline (classic primorial construction): {baseline} composites -> improvement x{L/baseline:.2f}")9899 # verify covering exhaustively before CRT (belt and braces)100 for i in range(1, L + 1):101 assert any(i % p == a for p, a in classes.items()), f"position {i} uncovered"102 for p, a in classes.items():103 assert 0 % p != a and (L + 1) % p != a, f"class of {p} hits an endpoint"104105 x, P = crt(classes)106 print(f"P = {m}# = {P}")107 # search smallest t with both endpoints prime; keep N + L + 1 under MR limit108 t_max = (MR_LIMIT - x - L - 1) // P109 found = None110 for t in range(1, t_max + 1):111 N = x + t * P112 if is_prime(N) and is_prime(N + L + 1):113 found = (t, N)114 break115 assert found, f"no prime endpoints for t <= {t_max}"116 t, N = found117 gap = L + 1118 merit = gap / log(N)119 print(f"t = {t}; N = {N} ({len(str(N))} digits)")120 print(f"CERTIFIED GAP: next_prime({N}) - {N} = {gap}, merit = {merit:.4f}, "121 f"csg = {gap/log(N)**2:.5f}")122123 # interior divisor table: smallest covering prime per position124 divisors = {}125 for i in range(1, L + 1):126 q = min(p for p, a in classes.items() if i % p == a)127 assert (N + i) % q == 0 and N + i > q128 divisors[i] = q129130 cert = {131 "title": "Certified prime desert via covering system",132 "author": "Simon-Pierre Boucher — contact@spboucher.ai",133 "date": "2026-08-06",134 "claim": f"The gap between consecutive primes N and N+{gap} is exactly {gap}.",135 "N": str(N),136 "gap": gap,137 "merit": round(merit, 5),138 "csg_ratio": round(gap / log(N) ** 2, 6),139 "construction": {140 "prime_set_max": m,141 "primorial_P": str(P),142 "crt_residue_x": str(x),143 "shift_t": t,144 "classes_a_p": {str(p): a for p, a in sorted(classes.items())},145 "note": "for EVERY t>=0, x+t*P+1 .. x+t*P+L are composite (covering); "146 "this specific t makes both endpoints prime",147 },148 "interior_divisors": {str(i): q for i, q in sorted(divisors.items())},149 "endpoint_primality": {150 "method": "deterministic Miller-Rabin, bases 2..37 (12 bases)",151 "validity_bound": str(MR_LIMIT),152 "both_endpoints_below_bound": bool(N + gap < MR_LIMIT),153 },154 "baseline_same_primes": baseline,155 "epistemic_status": "PROVEN (interior compositeness, by covering) + "156 "CERTIFIED (endpoint primality, deterministic MR). "157 "NOT a record (records.md: merit record is 41.94); "158 "value = fully certified pipeline.",159 }160 path = CERTS / "desert_certificate.json"161 with open(path, "w") as f:162 json.dump(cert, f, indent=2)163 print(f"certificate written: {path} ({time.time()-t0:.1f}s)")164165166if __name__ == "__main__":167 main()168