"""Certificat exact d'une majoration de la densite superieure de A = {n impair : n = p + 2^k}. Inegalite (argument d'obstruction d'Erdos, comme chez Habsieger-Roblot, Chen-Dai-Li, Griego, Yoo, Salavatov, Patankar) : pour tout ensemble fini P de premiers impairs, M = prod P, T = ppcm des ord_q(2), dbar(A) <= sum_{a mod M} min( 1/(2M), nu(a) / (T phi(M) log 2) ), nu(a) = #{ r mod T : pgcd(a - 2^r, M) = 1 }. P = base B (histogramme exact de nu_0 sur a mod M_0) + premiers hors base, regroupes par ordre d. Pour un groupe G d'ordre d, chaque q de G exclut soit rien (a mod q hors de <2>, q - d choix), soit une classe r = c_q mod d (d choix, c_q uniforme). Dans chaque bloc de classes qui ne different que par les choix du groupe G et qui ont le meme nombre j de classes exclues distinctes, la moyenne de nu vaut nu_reste * (1 - j/d) (l'ensemble des classes exclues est uniforme parmi les parties a j elements). Comme x -> min(1/2, x) est concave, remplacer chaque bloc par sa moyenne MAJORE la somme. Si d est premier avec la periode, c'est une egalite (grappes de Griego). D'ou S <= sum_{nu_0} (delta(nu_0)/M_0) * E_H[ min(1/2, kappa * nu_0 * H) ], kappa = M / (T_0 phi(M) lambda), H = produit sur les groupes de (d - j)/d, j de loi d'occupation exacte, lambda < log 2 rationnel. Les lois sont tenues en virgule fixe sur 2^S bits : multiplicateurs arrondis vers le haut, poids vers le bas, masse manquante comptee 1/2 ; fusion d'atomes voisins en leur moyenne (concavite). Chaque operation majore la somme. Classes au-dessus de la coupe de l'histogramme : comptees 1/2. Tout est en entiers et fractions exactes. """ import json, sys, gzip, time, hashlib sys.set_int_max_str_digits(0) from fractions import Fraction from math import lcm, prod S_BITS = 128 ONE = 1 << S_BITS def ord2(q): x, d = 2 % q, 1 while x != 1: x, d = x * 2 % q, d + 1 return d def primes_below(N): s = bytearray([1]) * N; s[0] = s[1] = 0 for i in range(2, int(N ** .5) + 1): if s[i]: s[i*i::i] = bytearray(len(s[i*i::i])) return [i for i in range(3, N) if s[i]] def lam_log2(): # 2 sum_{j<60} 1/((2j+1) 3^(2j+1)) < log 2 return 2 * sum(Fraction(1, (2 * j + 1) * 3 ** (2 * j + 1)) for j in range(60)) def occupancy(d, qs): """Loi exacte de j = nombre de classes distinctes exclues mod d : {j: effectif}, total prod(qs).""" st = {0: 1} for q in qs: nx = {} for j, c in st.items(): nx[j] = nx.get(j, 0) + c * (q - d + j) if j < d: nx[j + 1] = nx.get(j + 1, 0) + c * (d - j) st = nx assert sum(st.values()) == prod(qs) return st def cdiv(a, b): return -((-a) // b) def multiply(law, d, occ, W): """law : liste (h, w) en virgule fixe ; facteur (d-j)/d avec poids occ[j]/W.""" out = {} for h, w in law: for j, c in occ.items(): hn = cdiv(h * (d - j), d) # arrondi vers le haut wn = (w * c) // W # arrondi vers le bas if wn: out[hn] = out.get(hn, 0) + wn return sorted(out.items()) def compress(law, K): """Fusion d'atomes en leur moyenne ponderee (arrondie vers le haut), par cases d'une grille reguliere en log h. Toute partition donne un majorant (concavite) ; la grille ne sert qu'a perdre peu.""" if len(law) <= K: return law from math import log lo = log(law[0][0]); hi = log(law[-1][0]) step = (hi - lo) / K or 1.0 out = []; cur = None; W = HW = 0 for h, w in law: # law est triee par h b = min(int((log(h) - lo) / step), K - 1) if b != cur and W: out.append((cdiv(HW, W), W)); W = HW = 0 cur = b; W += w; HW += h * w if W: out.append((cdiv(HW, W), W)) return out def read_groups(path): """Paquets de classes (W, SN) : W classes, somme des nu egale a SN, tries par moyenne SN/W. Fichier .csv 'W,SN' (paquets) ; sinon histogramme exact 'nu c' (paquet d'une seule valeur).""" op = gzip.open if path.endswith('.gz') else open G = [] for line in op(path, 'rt'): if line.startswith('#') or not line.strip(): continue if path.endswith('.csv'): W, SN = line.strip().split(','); G.append((int(W), int(SN))) else: a, b = line.split(); G.append((int(b), int(b) * int(a))) if not path.endswith('.csv'): G.sort(key=lambda g: Fraction(g[1], g[0])) for (W1, S1), (W2, S2) in zip(G, G[1:]): assert W1 > 0 and S1 * W2 <= S2 * W1, "paquets non tries" return G def group_bins(bins, B): """Fusionne un histogramme exact (nu, c) trie en B paquets consecutifs (concavite : majorant).""" n = len(bins); out = [] for g in range(B): a, b = g * n // B, (g + 1) * n // B if a == b: continue out.append((sum(c for _, c in bins[a:b]), sum(c * v for v, c in bins[a:b]))) return out def build(base, extra, Q, K, log=print): """extra : {d: [q...]} premiers hors base imposes (grappes publiees) ; on ajoute tous les premiers < Q.""" used = set(base) groups = {} for d, qs in extra.items(): for q in qs: assert ord2(q) == int(d) and q not in used; used.add(q) groups.setdefault(int(d), []).append(q) for q in primes_below(Q): if q not in used: used.add(q); groups.setdefault(ord2(q), []).append(q) allp = sorted(used) M = prod(allp); phi = prod(q - 1 for q in allp) T0 = lcm(*[ord2(q) for q in base]) kappa = Fraction(M, T0 * phi) / lam_log2() law = [(ONE, ONE)] t = time.time() for i, d in enumerate(sorted(groups)): qs = sorted(groups[d]); occ = occupancy(d, qs) law = compress(multiply(law, d, occ, prod(qs)), K) lost = ONE - sum(w for _, w in law) assert lost >= 0 log("groupes %d, premiers hors base %d, atomes %d, masse perdue %.3e, %.0f s" % ( len(groups), sum(len(v) for v in groups.values()), len(law), lost / ONE, time.time() - t)) return law, lost, kappa, allp, groups def evaluate(G, M0, law, lost, kappa): """S = sum_paquets (W/M0) sum_j w_j min(1/2, kappa (SN/W) h_j) + masse perdue/2 + classes hors paquets/2.""" law = sorted(law) hs = [h for h, _ in law] pre_hw = [0]; pre_w = [0] for h, w in law: pre_hw.append(pre_hw[-1] + h * w); pre_w.append(pre_w[-1] + w) Wtot = pre_w[-1] kn, kd = kappa.numerator, kappa.denominator J = len(hs); acc = {}; tot = 0 for W, SN in G: # moyennes croissantes tot += W # regime lineaire pour l'atome j : 2 kappa (SN/W) h_j / ONE < 1 while J > 0 and not (2 * kn * SN * hs[J - 1] < kd * W * ONE): J -= 1 a = acc.setdefault(J, [0, 0]); a[0] += SN; a[1] += W above = M0 - tot; assert above >= 0 S = Fraction(above, 2 * M0) + Fraction(lost, 2 * ONE) for Jv, (sn, sw) in acc.items(): S += (kappa * sn * Fraction(pre_hw[Jv], ONE * ONE) + Fraction(sw * (Wtot - pre_w[Jv]), 2 * ONE)) / M0 return S def dec(x, n=40): from decimal import Decimal, getcontext getcontext().prec = n + 5 return Decimal(x.numerator) / Decimal(x.denominator) def run(cfgpath): import os here = os.path.dirname(os.path.abspath(cfgpath)) cfg = json.load(open(cfgpath)) base = cfg["base"]; extra = cfg.get("clusters", {}) Q = cfg["Q"]; K = cfg["K"] hist = os.path.join(here, cfg["histogram"]) h = hashlib.sha256() op = gzip.open if hist.endswith('.gz') else open with op(hist, 'rb') as f: for blk in iter(lambda: f.read(1 << 20), b''): h.update(blk) print(os.path.basename(cfgpath), ": histogramme", cfg["histogram"], "sha256", h.hexdigest(), flush=True) if "histogram_sha256" in cfg: assert h.hexdigest() == cfg["histogram_sha256"], "empreinte de l'histogramme" G = read_groups(hist) print("paquets", len(G), flush=True) M0 = prod(base) law, lost, kappa, allp, groups = build(base, extra, Q, K) S = evaluate(G, M0, law, lost, kappa) print("premiers au total", len(allp), " Q =", Q, " K =", K) print("S =", dec(S)) if "claim" in cfg: claim = Fraction(cfg["claim"]) assert S < claim, "la borne annoncee n'est pas atteinte" print("donc dbar(A) <", cfg["claim"], ": VERIFIE", flush=True) json.dump({"S_num": str(S.numerator), "S_den": str(S.denominator), "S": str(dec(S)), "primes": len(allp)}, open(cfgpath + ".S.json", "w")) return S def main(): import os if len(sys.argv) > 1: for p in sys.argv[1:]: run(p) else: here = os.path.dirname(os.path.abspath(__file__)) for p in ["cfg_theorem1.json", "cfg_theorem2.json"]: run(os.path.join(here, p)) if __name__ == "__main__": main()