/* Job 4291 control, independent of the fold: max cyclic gap of the true twin tile T_x, i.e. of {v mod 2*prod(3<=p<=x): v odd, gcd(v(v+2), P) = 1}, by a direct byte sieve over one period. Prints x, P, D, G2. */ #include #include #include #include int main(int argc, char **argv) { int x = atoi(argv[1]); int ps[16], np = 0; for (int p = 3; p <= x; p++) { int ok = 1; for (int d = 2; d * d <= p; d++) if (p % d == 0) ok = 0; if (ok) ps[np++] = p; } int64_t P = 2; for (int k = 0; k < np; k++) P *= ps[k]; unsigned char *bad = calloc(P, 1); for (int64_t v = 0; v < P; v += 2) bad[v] = 1; for (int k = 0; k < np; k++) { int p = ps[k]; for (int64_t v = 0; v < P; v += p) bad[v] = 1; for (int64_t v = p - 2; v < P; v += p) bad[v] = 1; } int64_t first = -1, prev = -1, D = 0, mg = 0; for (int64_t v = 0; v < P; v++) if (!bad[v]) { if (prev >= 0 && v - prev > mg) mg = v - prev; if (first < 0) first = v; prev = v; D++; } if (P + first - prev > mg) mg = P + first - prev; printf("%d %lld %lld %lld\n", x, (long long)P, (long long)D, (long long)mg); return 0; }