"""Test par force brute du principe : somme exacte <= majorant (grappes moyennees) <= somme sans les ajouts.""" import random, itertools from fractions import Fraction from math import lcm, prod, gcd import cert def exact_S(P, lam): M = prod(P); T = lcm(*[cert.ord2(q) for q in P]); phi = prod(q - 1 for q in P) pw = [pow(2, r, M) for r in range(T)] S = Fraction(0) for a in range(M): nu = sum(1 for r in range(T) if gcd(a - pw[r], M) == 1) S += min(Fraction(1, 2 * M), Fraction(nu, T * phi) / lam) return S def hist(B): M0 = prod(B); T0 = lcm(*[cert.ord2(q) for q in B]); pw = [pow(2, r, M0) for r in range(T0)] h = {} for a in range(M0): nu = sum(1 for r in range(T0) if gcd(a - pw[r], M0) == 1); h[nu] = h.get(nu, 0) + 1 return sorted(h.items()) def cert_S(B, extra, K): lam = cert.lam_log2() groups = {} for q in extra: groups.setdefault(cert.ord2(q), []).append(q) allp = sorted(set(B) | set(extra)); M = prod(allp); phi = prod(q - 1 for q in allp) T0 = lcm(*[cert.ord2(q) for q in B]); kappa = Fraction(M, T0 * phi) / lam law = [(cert.ONE, cert.ONE)] for d in sorted(groups): qs = groups[d]; law = cert.compress(cert.multiply(law, d, cert.occupancy(d, qs), prod(qs)), K) lost = cert.ONE - sum(w for _, w in law) return cert.evaluate([(c, c * v) for v, c in hist(B)], prod(B), law, lost, kappa) def run_all(): L = cert.lam_log2(); n = strict = 0 cases = [([3, 5], [7]), ([3, 5], [13]), ([3, 7], [5, 13]), ([5, 7], [3, 31]), ([3, 5, 7], [11]), ([3, 5, 7], [13, 17]), ([3, 7], [73]), ([3, 5], [17, 257]), ([7, 13], [3, 5]), ([3, 11], [23]), ([5, 13], [3, 7, 31]), ([3, 5, 7], [19]), ([3, 5, 7], [13]), ([3, 5, 13], [7, 17]), ([3, 7, 13], [5, 19]), ([5, 7, 13], [3, 17])] eps = Fraction(1, 10**30) orig = cert.lam_log2 try: for B, X in cases: if prod(B + X) * lcm(*[cert.ord2(q) for q in B + X]) > 3e7: continue for t in [1, 2, 3, 5, 10]: lam = L * t cert.lam_log2 = (lambda lam=lam: lam) se = exact_S(B + X, lam); sc = cert_S(B, X, 10**9); sc2 = cert_S(B, X, 2); sb = cert_S(B, [], 10**9) ok = se <= sc and se <= sc2 and sc <= sc2 + eps and sc2 <= sb + eps n += 1; strict += (se < sc - eps and sc < sb - eps) print(B, "+", X, "lambda x%d" % t, "exact %.9f majorant %.9f compresse %.9f sans ajout %.9f %s" % (se, sc, sc2, sb, "OK" if ok else "ECHEC"), flush=True) assert ok finally: cert.lam_log2 = orig print(n, "cas OK, dont", strict, "ou exact < majorant < sans ajout strictement") if __name__ == "__main__": run_all()