/* period_check.c -- route 27 pursue (job #1377): K*(Q) by STREAMING one period, not materialising it. Object. Level x, P = x#. Level-x slots are the r with gcd(r,P) = gcd(r+2,P) = 1. A slot at global position r is killed by q iff q | r or q | r+2. Slots repeat mod P and each kill repeats mod q with q not dividing P, so the joint (slot, killed) pattern has exact period M = P * prod(Q), and K*(Q) = the longest CYCLIC run of consecutive slots in one period under that anchored rule. Why this program exists. job #1376 enumerated the period explicitly, which is fine while M is small (8.7e6 at level 19) but impossible at level 23 (M = 6.47e9) and level 29 (M = 2.01e11). Here the period is never stored: block m of the period is the tile shifted by m*P, so the block's kill mask is a function of (m*P mod q) alone, and the run length is carried ACROSS block boundaries with O(1) state. Memory is one byte per slot per prime of Q. Usage: period_check LEVEL q1 [q2 ...] */ #include #include #include #include #include static int is_prime(int n) { if (n < 2) return 0; for (int d = 2; (long)d * d <= n; d++) if (n % d == 0) return 0; return 1; } int main(int argc, char **argv) { if (argc < 3) { fprintf(stderr, "usage: %s LEVEL q1 [q2 ...]\n", argv[0]); return 2; } int x = atoi(argv[1]); int nq = argc - 2; unsigned long long Q[8]; for (int j = 0; j < nq; j++) Q[j] = strtoull(argv[j + 2], NULL, 10); unsigned long long P = 1; for (int q = 2; q <= x; q++) if (is_prime(q)) P *= q; unsigned long long prod = 1; for (int j = 0; j < nq; j++) prod *= Q[j]; printf("level %d P=%llu Q={", x, P); for (int j = 0; j < nq; j++) printf("%s%llu", j ? "," : "", Q[j]); printf("} period M=%llu\n", P * prod); fflush(stdout); /* ---- enumerate the slots of one tile, storing r mod q for each q in Q (one byte per slot per q) ---- */ size_t cap = 1 << 20, n = 0; unsigned char **rm = malloc(sizeof(unsigned char *) * nq); for (int j = 0; j < nq; j++) rm[j] = malloc(cap); if (!rm[0]) { fprintf(stderr, "alloc failed\n"); return 3; } const unsigned long long CH = 1ULL << 24; /* chunk of positions */ unsigned char *bad = malloc(CH + 4); if (!bad) { fprintf(stderr, "alloc failed (chunk)\n"); return 3; } clock_t t0 = clock(); for (unsigned long long lo = 0; lo < P; lo += CH) { unsigned long long hi = lo + CH; if (hi > P) hi = P; unsigned long long span = (hi - lo) + 2; /* cover r+2 for r in [lo,hi) */ memset(bad, 0, span); for (int q = 2; q <= x; q++) { if (!is_prime(q)) continue; unsigned long long v = (lo / q) * q; if (v < lo) v += q; if (v < (unsigned long long)q) v = q; /* 0 is not a slot: leave it marked by q=2 anyway */ if (lo == 0) bad[0] = 1; /* r = 0 is not coprime to P */ for (; v < hi + 2; v += q) bad[v - lo] = 1; } for (unsigned long long r = lo; r < hi; r++) { if (bad[r - lo]) continue; if (bad[(r + 2) - lo]) continue; if (n == cap) { cap *= 2; for (int j = 0; j < nq; j++) { rm[j] = realloc(rm[j], cap); if (!rm[j]) { fprintf(stderr, "realloc failed\n"); return 3; } } } for (int j = 0; j < nq; j++) rm[j][n] = (unsigned char)(r % Q[j]); n++; } } double tsieve = (double)(clock() - t0) / CLOCKS_PER_SEC; printf("slots in one tile N=%zu sieve %.1fs\n", n, tsieve); fflush(stdout); /* ---- stream the prod(Q) blocks, carrying the run across block boundaries ---- */ t0 = clock(); unsigned long long best = 0, cur = 0, prefix = (unsigned long long)-1; for (unsigned long long m = 0; m < prod; m++) { unsigned long long a[8]; for (int j = 0; j < nq; j++) { unsigned long long s = ((m % Q[j]) * (P % Q[j])) % Q[j]; a[j] = (Q[j] - s) % Q[j]; /* kill iff r = a-2 or a (mod q) */ } for (size_t i = 0; i < n; i++) { int killed = 0; for (int j = 0; j < nq; j++) { unsigned char v = rm[j][i]; if (v == (unsigned char)a[j] || v == (unsigned char)((a[j] + Q[j] - 2) % Q[j])) { killed = 1; break; } } if (killed) cur++; else { if (prefix == (unsigned long long)-1) prefix = cur; if (cur > best) best = cur; cur = 0; } } } /* The number of slot visits is prod*n (what the inner loop actually does). It is NOT P*prod*n: multiplying by P overflows 64 bits at level 29 and the printed figure would be meaningless. */ unsigned long long visits = prod * (unsigned long long)n; if (prefix == (unsigned long long)-1) best = visits; /* every slot killed: the run is the whole period */ else if (prefix + cur > best) best = prefix + cur; /* the run that wraps the period seam */ double tscan = (double)(clock() - t0) / CLOCKS_PER_SEC; printf("K*(Q)=%llu period positions=%llu slot visits=%llu scan %.1fs\n", best, P * prod, visits, tscan); return 0; }