"""verify_tuple.py -- independent verifier of the admissible 234360000-tuple (C, embedded) Le programme C ci-dessous (SOURCE) est ecrit dans un repertoire temporaire, compile avec gcc -O2 et execute. Aucun argument n'est requis : les parametres de l'article sont fixes dans ARGS (on peut les changer en ligne de commande). """ import os, subprocess, sys, tempfile ARGS = ['234360000', '2445670867', '50100', '20000', 'removed_gaps_1.csv,removed_gaps_2.csv'] SOURCE = r"""/* verif.c -- verificateur independant du k-uplet de H_5. Ensemble : E = {+-m : m in A}, A = {1} U {q premier : P0 < q <= a} prive des premiers listes dans RETIRES (un par ligne). Verifie : (1) |E| = K et a in A (donc diametre exactement 2a) ; (2) pour CHAQUE premier p <= K, une classe residuelle mod p ne rencontre pas E : d'abord la classe 0 (balayage direct de tous les multiples de p dans [0, a]), sinon la paire c, -c (c = 1..BUD), balayee directement. Le crible est un crible d'Eratosthene simple sur octets (code distinct du constructeur, qui crible les impairs en bits). Usage : ./verif K a P0 BUD RETIRES_ECARTS */ #include #include #include #include int main(int argc, char **argv) { int64_t K = atoll(argv[1]), a = atoll(argv[2]), P0 = atoll(argv[3]), BUD = atoll(argv[4]); uint8_t *A = malloc(a + 1); /* A[m] = 1 si m dans A */ memset(A, 1, a + 1); A[0] = 0; /* premiers <= sqrt(a) */ int64_t r = 1; while ((r + 1) * (r + 1) <= a) r++; uint8_t *small = calloc(r + 1, 1); int64_t ns = 0; int64_t *sp = malloc((r + 1) * sizeof(int64_t)); for (int64_t i = 2; i <= r; i++) if (!small[i]) { sp[ns++] = i; for (int64_t j = i * i; j <= r; j += i) small[j] = 1; } /* composites */ for (int64_t i = 0; i < ns; i++) { int64_t p = sp[i]; for (int64_t j = p * p; j <= a; j += p) A[j] = 0; } /* A contient maintenant 1 et les premiers <= a ; on retire les premiers <= P0 */ for (int64_t m = 2; m <= P0 && m <= a; m++) A[m] = 0; /* premiers retires */ FILE *f = fopen(argv[5], "r"); int64_t q = 0, g, nr = 0; /* fichier : ecarts successifs, q = somme cumulee */ while (fscanf(f, "%lld", (long long *)&g) == 1) { if (g <= 0) { fprintf(stderr, "ecart non positif\n"); return 1; } q += g; if (q < 2 || q > a) { if (q > a) continue; fprintf(stderr, "retire invalide %lld\n", (long long)q); return 1; } if (!A[q]) { fprintf(stderr, "retire %lld absent ou non premier > P0\n", (long long)q); return 1; } A[q] = 0; nr++; } fclose(f); int64_t na = 0; for (int64_t m = 1; m <= a; m++) na += A[m]; printf("|A| = %lld, |E| = %lld, retires effectifs = %lld, a dans A : %d\n", (long long)na, (long long)(2 * na), (long long)nr, A[a]); if (2 * na != K || !A[a]) { printf("ECHEC : cardinal ou extremite\n"); return 1; } /* premiers <= K : on les recalcule par un crible separe (K <= a) */ uint8_t *cK = calloc(K + 1, 1); for (int64_t i = 2; i * i <= K; i++) if (!cK[i]) for (int64_t j = i * i; j <= K; j += i) cK[j] = 1; int64_t np = 0, n0 = 0, nc = 0, maxc = 0; for (int64_t p = 2; p <= K; p++) { if (cK[p]) continue; np++; int ok0 = 1; for (int64_t m = p; m <= a; m += p) if (A[m]) { ok0 = 0; break; } if (ok0) { n0++; continue; } int ok = 0; for (int64_t c = 1; c <= BUD && c <= (p - 1) / 2; c++) { int occ = 0; for (int64_t m = c; m <= a; m += p) if (A[m]) { occ = 1; break; } if (!occ) for (int64_t m = p - c; m <= a; m += p) if (A[m]) { occ = 1; break; } if (!occ) { ok = 1; nc++; if (c > maxc) maxc = c; break; } } if (!ok) { printf("ECHEC : aucune classe vide trouvee pour p = %lld\n", (long long)p); return 1; } } printf("premiers p <= K : %lld ; classe 0 vide : %lld ; paire +-c vide : %lld (c max %lld)\n", (long long)np, (long long)n0, (long long)nc, (long long)maxc); printf("ADMISSIBLE : k = %lld, diametre = %lld\n", (long long)K, (long long)(2 * a)); return 0; } """ def main(): args = sys.argv[1:] or ARGS d = tempfile.mkdtemp() c = os.path.join(d, "prog.c"); exe = os.path.join(d, "prog") open(c, "w").write(SOURCE) subprocess.run(["gcc", "-O2", "-o", exe, c], check=True) here = os.path.dirname(os.path.abspath(__file__)) args = [os.path.join(here, x) if os.path.exists(os.path.join(here, x)) else x for x in args] # le fichier des ecarts peut etre donne en plusieurs morceaux separes par des virgules : # on les met bout a bout dans l'ordre (les ecarts se cumulent d'un morceau a l'autre) parts = [os.path.join(here, x) if os.path.exists(os.path.join(here, x)) else x for x in args[4].split(",")] joined = os.path.join(d, "gaps.csv") with open(joined, "w") as out: for p in parts: t = open(p).read() out.write(t if t.endswith("\n") else t + "\n") args[4] = joined r = subprocess.run([exe] + args) sys.exit(r.returncode) if __name__ == "__main__": main()