"""build_tuple.py -- construction of the tuple and of the certificate of classes (C, embedded); writes classes.txt (about 164 MB) 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', '2500000000', '50100', '20000', 'classes.txt'] SOURCE = r"""/* sym.c -- k-uplet admissible symetrique pour H_5. Ensemble E = {+-1} U {+-q : q premier, P0 < q <= X} prive des +-p "retires". Admissibilite : pour p <= P0 la classe 0 mod p est vide (aucun element divisible par p, car X < P0^2) ; pour P0 < p <= K on cherche c avec la classe c (et donc -c, par symetrie) vide ; a defaut (budget BUD essais) on retire +-p, ce qui vide la classe 0 (les autres multiples de p dans [-X, X] sont composes). On traite les premiers de K vers P0 : un retrait ne peut que vider des classes deja verifiees. Sortie : nombre d'elements, nombre de retraits, puis la plus petite fenetre symetrique [-a, a] contenant K elements et la meilleure fenetre [u, v] (balayage exact) ; ecrit la liste des premiers retires et des classes trouvees si demande. Usage : ./sym K X P0 BUD [fichier_sortie] */ #include #include #include #include static uint8_t *B; /* bit m (m impair, 1 <= m <= X) : m appartient a E (cote positif) */ static inline int get(int64_t m) { return (B[m >> 4] >> ((m >> 1) & 7)) & 1; } static inline void clr(int64_t m) { B[m >> 4] &= (uint8_t)~(1u << ((m >> 1) & 7)); } int main(int argc, char **argv) { int64_t K = atoll(argv[1]), X = atoll(argv[2]), P0 = atoll(argv[3]), BUD = atoll(argv[4]); FILE *out = argc > 5 ? fopen(argv[5], "w") : NULL; if (X >= P0 * P0) { fprintf(stderr, "il faut X < P0^2\n"); return 1; } int64_t nb = (X >> 4) + 2; B = malloc(nb); memset(B, 0xFF, nb); /* crible d'Eratosthene sur les impairs <= X : B = premiers impairs */ clr(1); for (int64_t i = 3; i * i <= X; i += 2) if (get(i)) for (int64_t j = i * i; j <= X; j += 2 * i) clr(j); for (int64_t m = X + 1 + (X % 2 == 0); m < (nb << 4); m += 2) clr(m); /* au-dela de X */ /* on retire les premiers <= P0 ; on remet 1 */ for (int64_t m = 3; m <= P0; m += 2) clr(m); B[0] |= 1; /* m = 1 */ /* premiers <= K (tableau) */ uint8_t *c = calloc(K + 1, 1); for (int64_t i = 2; i * i <= K; i++) if (!c[i]) for (int64_t j = i * i; j <= K; j += i) c[j] = 1; int64_t nret = 0, ntest = 0, nfree = 0; for (int64_t p = K; p > P0; p--) { if (c[p] || p < 3) continue; int found = -1; for (int64_t cc = 1; cc <= (p - 1) / 2 && cc <= BUD; cc++) { int occ = 0; for (int64_t m = cc; m <= X; m += p) if ((m & 1) && get(m)) { occ = 1; break; } if (!occ) for (int64_t m = p - cc; m <= X; m += p) if ((m & 1) && get(m)) { occ = 1; break; } ntest++; if (!occ) { found = (int)cc; break; } } if (found >= 0) { nfree++; if (out) fprintf(out, "C %lld %d\n", (long long)p, found); } else { if (p <= X && get(p)) clr(p); nret++; if (out) fprintf(out, "R %lld\n", (long long)p); } } /* comptage et fenetres */ int64_t npos = 0; for (int64_t m = 1; m <= X; m += 2) npos += get(m); int64_t total = 2 * npos; printf("K=%lld X=%lld P0=%lld BUD=%lld : elements=%lld retraits=%lld classes_vides=%lld essais=%lld\n", (long long)K, (long long)X, (long long)P0, (long long)BUD, (long long)total, (long long)nret, (long long)nfree, (long long)ntest); if (total < K) { printf("PAS ASSEZ D'ELEMENTS\n"); return 0; } /* fenetre symetrique minimale : plus petit a avec 2 * #{m <= a} >= K */ int64_t cum = 0, a = 0; for (int64_t m = 1; m <= X; m += 2) { cum += get(m); if (2 * cum >= K) { a = m; break; } } printf("fenetre symetrique [-%lld, %lld] : diametre %lld (elements %lld)\n", (long long)a, (long long)a, (long long)(2 * a), (long long)(2 * cum)); if (out) fclose(out); 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] r = subprocess.run([exe] + args) sys.exit(r.returncode) if __name__ == "__main__": main()