"""previous_record_width.py -- width of the tuple of the k smallest primes > k (previous record), k = 234360000 (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', '234360001', '0', '0'] SOURCE = r"""/* crible.c -- k-uplet admissible par construction : pour chaque premier p <= K on exclut une classe r_p mod p. Regle : r_p = 1 si p <= M (crible de Schinzel), r_p = 0 sinon ; r_2 = R2. Les survivants n >= S (n entier, S peut etre negatif) sont pris dans l'ordre ; on s'arrete au K-ieme. Sortie : premier survivant, K-ieme survivant, diametre = difference. Usage : ./crible K S M R2 */ #include #include #include #include static int64_t mod(int64_t a, int64_t p) { int64_t r = a % p; return r < 0 ? r + p : r; } int main(int argc, char **argv) { int64_t K = atoll(argv[1]), S = atoll(argv[2]), M = atoll(argv[3]); int R2 = atoi(argv[4]); /* premiers <= K */ uint8_t *c = calloc(K + 1, 1); int64_t np = 0; 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; for (int64_t i = 2; i <= K; i++) if (!c[i]) np++; int64_t *P = malloc(np * sizeof(int64_t)), *nx = malloc(np * sizeof(int64_t)); np = 0; for (int64_t i = 2; i <= K; i++) if (!c[i]) P[np++] = i; free(c); for (int64_t i = 0; i < np; i++) { int64_t p = P[i], r = (p == 2) ? R2 : (p <= M ? 1 : 0); nx[i] = mod(r - S, p); /* premier decalage t >= 0 avec S + t = r mod p */ } const int64_t L = 1 << 25; uint8_t *seg = malloc(L); int64_t cnt = 0, first = INT64_MIN, last = 0, base = 0; while (cnt < K) { memset(seg, 1, L); for (int64_t i = 0; i < np; i++) { int64_t p = P[i], t = nx[i]; for (; t < base + L; t += p) seg[t - base] = 0; nx[i] = t; } for (int64_t t = 0; t < L && cnt < K; t++) if (seg[t]) { cnt++; if (first == INT64_MIN) first = S + base + t; last = S + base + t; } base += L; } printf("K=%lld S=%lld M=%lld R2=%d premiers=%lld premier=%lld dernier=%lld diametre=%lld\n", (long long)K, (long long)S, (long long)M, R2, (long long)np, (long long)first, (long long)last, (long long)(last - first)); 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()