"""verif_py.py -- second verificateur (Python + numpy), independant de verif.c. Ensemble E = {+-m : m in A}, A = {1} U {q premier : P0 < q <= a} prive des premiers listes dans RETIRES. Certificat CLASSES : lignes "C p c" (paire de classes +-c vide mod p) et "R p" (p retire : classe 0 vide). Verifie : |E| = K, a dans A ; pour chaque premier p <= K : p <= P0 (classe 0 vide car A ne contient que 1 et des premiers > P0), ou ligne R (p absent de A, donc classe 0 vide), ou ligne C (balayage direct des deux progressions c et p - c dans [0, a]). Chaque premier p <= K doit avoir exactement une ligne si p > P0. Usage : python3 verif_py.py K a P0 CLASSES """ import sys, time, numpy as np K, a, P0, CL = int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]), sys.argv[4] t0 = time.time() def log(*x): print(f"[{time.time() - t0:7.0f}s]", *x, flush=True) # crible des impairs : odd[i] <-> m = 2i + 1, m <= a n = (a - 1) // 2 + 1 odd = np.ones(n, dtype=np.bool_); odd[0] = False # 1 n'est pas premier r = int(a ** 0.5) + 1 for p in range(3, r + 1, 2): if odd[(p - 1) // 2]: odd[(p * p - 1) // 2::p] = False log("crible fait") # A = {1} U premiers impairs > P0, prive des retires lines = open(CL).read().split("\n") R, C = [], [] for L in lines: if not L: continue t = L.split() if t[0] == "R": R.append(int(t[1])) else: C.append((int(t[1]), int(t[2]))) R = np.array(R, dtype=np.int64); Cp = np.array([x[0] for x in C], dtype=np.int64); Cc = np.array([x[1] for x in C], dtype=np.int64) log("certificat lu :", len(R), "R,", len(C), "C") odd[1:(P0 - 1) // 2 + 1] = False # premiers impairs 3..P0 exclus assert odd[(R[R <= a] - 1) // 2].all(), "un retire n'est pas un element" odd[(R[R <= a] - 1) // 2] = False odd[0] = True # m = 1 cnt = int(odd.sum()) log("|A| =", cnt, " |E| =", 2 * cnt, " a dans A :", bool(odd[(a - 1) // 2])) assert 2 * cnt == K and odd[(a - 1) // 2] and a % 2 == 1 # premiers <= K : ceux de la table (2 et impairs premiers), recalcules par le meme crible avant modification -> on refait pk = np.ones(K + 1, dtype=np.bool_); pk[:2] = False for p in range(2, int(K ** 0.5) + 1): if pk[p]: pk[p * p::p] = False primes = np.nonzero(pk)[0] big = primes[primes > P0] allp = np.concatenate([R, Cp]); allp.sort() assert len(allp) == len(big) and (allp == big).all(), "chaque premier P0 < p <= K doit avoir exactement une ligne" log("couverture des premiers ok :", len(big), "premiers > P0,", int((primes <= P0).sum()), "premiers <= P0") # lignes C : progressions m = c + j p et m = p - c + j p dans [1, a], parmi les impairs seulement assert ((Cc >= 1) & (2 * Cc < Cp)).all() bad = 0; done = 0; B = 2_000_000 order = np.argsort(Cp) Cp, Cc = Cp[order], Cc[order] for start in range(0, len(Cp), 20000): p = Cp[start:start + 20000]; c = Cc[start:start + 20000] for base in (c, p - c): # premier terme impair : base ou base + p (p impair) f = np.where(base % 2 == 1, base, base + p) step = 2 * p L = np.where(f <= a, (a - f) // step + 1, 0) tot = int(L.sum()) idx = np.repeat(np.arange(len(p)), L) off = np.arange(tot) - np.repeat(np.cumsum(L) - L, L) m = f[idx] + off * step[idx] hit = odd[(m - 1) // 2] if hit.any(): bad += int(np.unique(idx[hit]).size) done += len(p) if start % 2_000_000 == 0: log("lignes C verifiees :", done) log("lignes C en echec :", bad) assert bad == 0 print(f"ADMISSIBLE (verif_py) : k = {K}, diametre = {2 * a}")