#!/usr/bin/env python3 """Job #1288 (route 22, pursue): does the level-X exact-count LP certificate grow with p? Object (unchanged from uset_level_lp2.py, #559): level p has killers P = primes 5..p (m of them), p' = next prime, window X = p'^2, positions n = 5 mod 6 with p' <= n and n+2 < X. A position's TYPE is the set of killers dividing n(n+2); survivors (empty type) are exactly the zone twins. For a killer set R, N_R = #positions whose type contains R, computed exactly here. The LP minimise x_empty subject to sum_{T superset of R} x_T = N_R for every R with prod(R) <= D, x >= 0 has the true type distribution as a feasible point, so its optimum is a valid lower bound on the zone twin count, and by duality the best such bound from level-D data. Three things this adds to #559: * ATOM RESTRICTION. x is indexed by killer sets T with prod(T) <= X^2, not by all 2^m subsets. Valid because prod(T) divides n(n+2) < X^2 for a real position, and the restricted LP still contains the true point, so its optimum is still a lower bound on the twin count (and is >= the unrestricted optimum, since dropping columns shrinks the feasible set). --compare checks the two against each other where both are tractable. * EXACT CERTIFICATION, no exact LP solver. Take the floating dual y, round it to rationals, and repair it: the empty set is a subset of EVERY column, so lowering y_empty by delta lowers every dual row sum by delta. With delta = the exact maximum violation, the shifted y is exactly dual feasible, and sum_R y_R N_R computed in Fractions is then a rigorous lower bound on the LP optimum, hence on the twin count (weak duality). Same device as return #562 on route 8. * The SPLIT atom restriction (--split), a strictly sharper valid rule: a real position's killers divide n(n+2), so T splits into A | n and B | n+2 with prod(A), prod(B) < X. stdout is the artifact (one JSON object per level, plus a final summary); progress and timings go to stderr. Deterministic: no randomness anywhere. """ import argparse, itertools, json, math, sys, time from fractions import Fraction import numpy as np from scipy.optimize import linprog from scipy.sparse import csr_matrix T0 = time.process_time() def log(o): print(json.dumps(o), file=sys.stderr, flush=True) def isprime(q): return q > 1 and all(q % r for r in range(2, int(q ** 0.5) + 1)) def subsets_with_product(P, cap, universe=None): """Every subset (as a bitmask over P's indices) whose product is <= cap.""" idx = range(len(P)) if universe is None else universe idx = sorted(idx) out = [] def rec(k, mask, prod): if k == len(idx): out.append(mask) return rec(k + 1, mask, prod) i = idx[k] if prod * P[i] <= cap: rec(k + 1, mask | (1 << i), prod * P[i]) rec(0, 0, 1) return out def splittable(P, mask, X): """Can T be split into A | n, B | n+2 with prod(A) < X and prod(B) < X?""" els = [P[i] for i in range(len(P)) if mask >> i & 1] if math.prod(els) >= X * X: return False for r in range(len(els) + 1): for c in itertools.combinations(els, r): a = math.prod(c) if a < X and math.prod(els) // a < X: return True return False def level(p, exponents=(1.0, 1.25), restricted=True, split=False, unrestricted=False, certify=False, denom=10 ** 12): P = [q for q in range(5, p + 1) if isprime(q)] m = len(P) pn = next(q for q in range(p + 1, 10 * p) if isprime(q)) X = pn * pn pos = [n for n in range(pn, X - 2) if n % 6 == 5] masks = {} for n in pos: t = 0 for i, q in enumerate(P): if n % q == 0 or (n + 2) % q == 0: t |= 1 << i masks[t] = masks.get(t, 0) + 1 twins = masks.get(0, 0) log({'level': p, 'm': m, 'X': X, 'positions': len(pos), 'twins': twins, 'distinct_types': len(masks), 'cpu': round(time.process_time() - T0, 1)}) out = {'p': p, 'm': m, 'X': X, 'positions': len(pos), 'twins': twins, 'distinct_types': len(masks), 'results': {}} for expo in exponents: D = int(X ** expo) rows = subsets_with_product(P, D) row_of = {r: i for i, r in enumerate(rows)} # exact N_R: every subset of a realised type that is a row gets that type's count b = np.zeros(len(rows), dtype=float) bexact = [0] * len(rows) for t, c in masks.items(): els = [i for i in range(m) if t >> i & 1] for r in subsets_with_product(P, D, universe=els): j = row_of[r] b[j] += c bexact[j] += c for kind in (['restricted'] if restricted else []) + (['split'] if split else []) \ + (['unrestricted'] if unrestricted and m <= 16 else []): t1 = time.process_time() if kind == 'unrestricted': cols = list(range(1 << m)) elif kind == 'restricted': cols = subsets_with_product(P, X * X) else: cols = [t for t in subsets_with_product(P, X * X) if splittable(P, t, X)] ri, ci = [], [] for j, T in enumerate(cols): els = [i for i in range(m) if T >> i & 1] for r in subsets_with_product(P, D, universe=els): ri.append(row_of[r]) ci.append(j) A = csr_matrix((np.ones(len(ri)), (np.array(ri), np.array(ci))), shape=(len(rows), len(cols))) c = np.zeros(len(cols)) c[cols.index(0)] = 1.0 lp = linprog(c, A_eq=A, b_eq=b, bounds=(0, None), method='highs') rec = {'D_exponent': expo, 'rows': len(rows), 'columns': len(cols), 'nonzeros': len(ri), 'status': int(lp.status), 'objective': None if lp.fun is None else float(lp.fun), 'cpu_seconds': round(time.process_time() - t1, 2)} if certify and lp.status == 0: y = lp.eqlin.marginals yq = [Fraction(int(round(v * denom)), denom) for v in y] # exact dual feasibility: max over columns of sum_{R subset of T} y_R worst = Fraction(0) for j, T in enumerate(cols): els = [i for i in range(m) if T >> i & 1] s = sum(yq[row_of[r]] for r in subsets_with_product(P, D, universe=els)) s -= Fraction(1) if T == 0 else Fraction(0) # c_T if s > worst: worst = s yq[row_of[0]] -= worst # empty set sits under every column bound = sum(q * n for q, n in zip(yq, bexact)) rec['exact'] = {'denominator': denom, 'shift': str(worst), 'certified_bound': str(bound), 'certified_floor': math.floor(bound), 'gap_to_float': None if lp.fun is None else float(lp.fun) - float(bound)} out['results'][f'{kind}@X^{expo}'] = rec log({'level': p, 'kind': kind, 'expo': expo, **{k: rec[k] for k in ('rows', 'columns', 'nonzeros', 'objective', 'cpu_seconds')}, 'certified': rec.get('exact', {}).get('certified_floor')}) return out def main(): ap = argparse.ArgumentParser() ap.add_argument('--levels', default='71,89,101,113,127,151') ap.add_argument('--exponents', default='1.0,1.25') ap.add_argument('--compare', action='store_true', help='also solve the unrestricted LP (m <= 16)') ap.add_argument('--split', action='store_true', help='also solve the sharper split-atom LP') ap.add_argument('--certify', action='store_true', help='exact rational dual certificate') ap.add_argument('--denominator', type=int, default=10 ** 12) a = ap.parse_args() rows = [] for p in [int(x) for x in a.levels.split(',')]: rows.append(level(p, exponents=[float(x) for x in a.exponents.split(',')], unrestricted=a.compare, split=a.split, certify=a.certify, denom=a.denominator)) print(json.dumps(rows[-1], sort_keys=True), flush=True) print(json.dumps({'summary': [{'p': r['p'], 'twins': r['twins'], **{k: v['objective'] for k, v in r['results'].items()}, **{f'certified {k}': v.get('exact', {}).get('certified_floor') for k, v in r['results'].items() if 'exact' in v}} for r in rows], 'total_cpu_seconds': round(time.process_time() - T0, 1)}, sort_keys=True)) if __name__ == '__main__': main()