/* Job 4291 (route 71 pursuit): gate trajectory gamma of every dihedral class of T_7's word class, levels 7, 11, 13, 17, 19, 23. Fold convention identical to gate2810.py / #1419: positions of the representative from 0, lifts v + jP laid out j-major (already increasing since 0 <= v < P), delete lifts = 0 or -2 mod q, gap word of the survivors including the wrap gap qP + K[0] - K[last]. Levels 11..19 are built as position arrays; the level-23 max gap is computed twice without building the 7,952,175-point set: A (scan): one pass over all 23*D lifts, tracking the previous survivor (the same j-major order); B (runs): max(old max gap, max over maximal runs of consecutive deleted lifts of the survivor distance across the run) -- every old gap survives in >= 19 of its 23 lifts, so the old max persists. A != B aborts. Input: reps4291.txt (first line "TRUE ..." then one representative per line). Output: one line per class, "idx g7 g11 g13 g17 g19 g23", the true word as idx -1. Usage: gate4291 reps.txt nthreads > out gate4291b (this file with -DDEPTH6): builds level 23 as well (G23 from the build) and computes the level-29 max gap by B (runs); every 500th class and the true word also run A (scan) at 29, A != B aborts. Output adds g29. */ #include #include #include #include #include #define MAXC 45200 #define L7 15 static int nrep; static int W[MAXC + 1][L7]; /* W[0] = true word */ static int G[MAXC + 1][7]; static int nthreads; static volatile int abort_flag = 0; typedef struct { int64_t *a, *b; } buf_t; /* fold position set S (size D, modulus P, increasing, S[0] = 0 not required) by q into out; returns new size, sets *maxgap */ static int64_t fold(const int64_t *S, int64_t D, int64_t P, int q, int64_t *out, int64_t *maxgap) { int64_t n = 0, mg = 0; int dq = (q - 2) % q; for (int j = 0; j < q; j++) { int64_t off = (int64_t)j * P; for (int64_t i = 0; i < D; i++) { int64_t v = S[i] + off; int r = (int)(v % q); if (r == 0 || r == dq) continue; if (n) { int64_t g = v - out[n - 1]; if (g > mg) mg = g; } out[n++] = v; } } int64_t w = (int64_t)q * P + out[0] - out[n - 1]; if (w > mg) mg = w; *maxgap = mg; return n; } /* A: level-q max gap by a full scan of lifts, no storage */ static int64_t scan_max(const int64_t *S, int64_t D, int64_t P, int q) { int64_t first = -1, prev = -1, mg = 0; int dq = (q - 2) % q; int *rs = malloc(sizeof(int) * D); for (int64_t i = 0; i < D; i++) rs[i] = (int)(S[i] % q); int Pq = (int)(P % q); for (int j = 0; j < q; j++) { int o = (int)(((int64_t)j * Pq) % q); int64_t off = (int64_t)j * P; for (int64_t i = 0; i < D; i++) { int r = rs[i] + o; if (r >= q) r -= q; if (r == 0 || r == dq) continue; int64_t v = S[i] + off; if (prev >= 0) { if (v - prev > mg) mg = v - prev; } else first = v; prev = v; } } int64_t w = (int64_t)q * P + first - prev; if (w > mg) mg = w; free(rs); return mg; } /* B: runs of deleted lifts. Lift (i, j) has value S[i] + jP; cyclic order index t = j*D + i. Deleted iff (S[i] + jP) mod q in {0, q-2}; for each i exactly two j are deleted. For each deleted lift whose predecessor is a survivor, walk forward to the next survivor; distance = value(next) - value(prev), cyclic mod qP. */ static int64_t runs_max(const int64_t *S, int64_t D, int64_t P, int q, int64_t oldmax) { int Pq = (int)(P % q), inv = 0; for (int k = 1; k < q; k++) if ((k * Pq) % q == 1) inv = k; int dq = (q - 2) % q; int64_t M = (int64_t)q * P, mg = oldmax; int *j0 = malloc(sizeof(int) * D), *j1 = malloc(sizeof(int) * D); for (int64_t i = 0; i < D; i++) { int r = (int)(S[i] % q); j0[i] = (int)((((int64_t)(0 - r + q) % q) * inv) % q); j1[i] = (int)((((int64_t)(dq - r + q) % q) * inv) % q); } #define DEL(i, j) (j0[i] == (j) || j1[i] == (j)) #define VAL(i, j) (S[i] + (int64_t)(j) * P) for (int64_t i = 0; i < D; i++) for (int c = 0; c < 2; c++) { int j = c ? j1[i] : j0[i]; int64_t pi = i - 1; int pj = j; if (pi < 0) { pi = D - 1; pj = (j + q - 1) % q; } if (DEL(pi, pj)) continue; /* not a run start */ int64_t ni = i; int nj = j; int64_t steps = 0; while (DEL(ni, nj)) { ni++; if (ni == D) { ni = 0; nj = (nj + 1) % q; } if (++steps > q * D) { abort_flag = 1; break; } } int64_t d = VAL(ni, nj) - VAL(pi, pj); d %= M; if (d < 0) d += M; if (d > mg) mg = d; } free(j0); free(j1); return mg; } static void *work(void *arg) { int tid = (int)(intptr_t)arg; #ifdef DEPTH6 int64_t cap = 7952175 + 16; #else int64_t cap = 378675 + 16; #endif int64_t *a = malloc(sizeof(int64_t) * cap), *b = malloc(sizeof(int64_t) * cap); static const int qs[4] = {11, 13, 17, 19}; for (int c = tid; c <= nrep; c += nthreads) { int64_t D = L7, P = 0, mg = 0; for (int k = 0; k < L7; k++) { a[k] = P; P += W[c][k]; if (W[c][k] > mg) mg = W[c][k]; } G[c][0] = (int)mg; for (int l = 0; l < 4; l++) { int64_t nD = fold(a, D, P, qs[l], b, &mg); int64_t *t = a; a = b; b = t; D = nD; P *= qs[l]; G[c][l + 1] = (int)mg; } #ifdef DEPTH6 { int64_t nD = fold(a, D, P, 23, b, &mg); int64_t *t = a; a = b; b = t; D = nD; P *= 23; G[c][5] = (int)mg; } int64_t B = runs_max(a, D, P, 29, mg); if (c == 0 || c % 500 == 0) { int64_t A = scan_max(a, D, P, 29); if (A != B) { fprintf(stderr, "MISMATCH29 class %d: scan %lld runs %lld\n", c, (long long)A, (long long)B); abort_flag = 1; } } G[c][6] = (int)B; #else int64_t A = scan_max(a, D, P, 23), B = runs_max(a, D, P, 23, mg); if (A != B) { fprintf(stderr, "MISMATCH class %d: scan %lld runs %lld\n", c, (long long)A, (long long)B); abort_flag = 1; } G[c][5] = (int)A; #endif if (tid == 0 && c % 4000 == 0) fprintf(stderr, "class %d D19=%lld P19=%lld\n", c, (long long)D, (long long)P); } free(a); free(b); return NULL; } int main(int argc, char **argv) { FILE *f = fopen(argv[1], "r"); nthreads = atoi(argv[2]); char line[512]; int n = 0; while (fgets(line, sizeof line, f)) { char *p = line; if (!strncmp(p, "TRUE ", 5)) p += 5; for (int k = 0; k < L7; k++) W[n][k] = (int)strtol(p, &p, 10); n++; } fclose(f); nrep = n - 1; pthread_t th[64]; for (int t = 0; t < nthreads; t++) pthread_create(&th[t], NULL, work, (void *)(intptr_t)t); for (int t = 0; t < nthreads; t++) pthread_join(th[t], NULL); if (abort_flag) { fprintf(stderr, "ABORT\n"); return 2; } for (int c = 0; c <= nrep; c++) #ifdef DEPTH6 printf("%d %d %d %d %d %d %d %d\n", c - 1, G[c][0], G[c][1], G[c][2], G[c][3], G[c][4], G[c][5], G[c][6]); #else printf("%d %d %d %d %d %d %d\n", c - 1, G[c][0], G[c][1], G[c][2], G[c][3], G[c][4], G[c][5]); #endif return 0; }