/* lagspec.c -- job 2783 (route 82 pursuit): exact lag spectrum of fold-kill runs on the twin tile T_x = {r mod x# : gcd(r(r+2), x#) = 1}, one full period, streaming, constant memory. Sieve: verbatim from work/2802/tcensus.c (job 2802): openers r = 30 j + c, c in {11, 17, 29}, per-class bitmaps over j, wheel pattern for q = 7, 11, 13, 17 plus strikes for 19 <= q <= x; a segment's look-ahead past n is the wrap. Statistic (route 82, returns #1025/#1296/#1394): cyclic gap word g_0 .. g_{D-1} (gap from each opener to the next), kill class S_p = {g : g mod p in {0, 2, p-2}}, m_p = #{i : g_i in S_p}, K_k(p) = #{i : g_i in S_p and g_{(i+k) mod D} in S_p}, k = 1..LAGS (K_1 is the route's K2). Also the gap histogram h_g and R_g = #{i : g_i = g_{i+1} = g} (repeat ratio R/E_rep and the forced-zero class). Method: per fold a 64-bit history of kill indicators inside a segment; each kill gap adds 1 to K_k for every set history bit k-1. Each segment also keeps its first and last 64 gaps; pairs that cross a segment boundary (including the cyclic wrap) are counted centrally from those. Every segment must hold >= LAGS gaps (checked). Output: JSON on stdout (no timings); progress and timing on stderr. Usage: lagspec cc -O2 -o lagspec lagspec.c -lpthread */ #include #include #include #include #include #ifndef SEGW #define SEGW 65536 #endif #define EXTW 8 #define PATW 17017 #define MAXG 4096 #define LAGS 64 #define MAXF 16 #define HV 128 /* gap-value index h = g/6 for the lag-1/lag-2 value-pair matrices */ static const int CLS[3] = {11, 17, 29}; static int X, NT, nstrike, sq[16], NF, FP[MAXF]; static uint64_t n, nwords, nseg; static uint64_t *pat[3]; static int64_t sres[3][16][2]; static volatile uint64_t nextseg = 0; static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER; static uint16_t killb[MAXG + 1]; static uint64_t Ng[MAXG + 1], Rg[MAXG + 1], Kk[MAXF][LAGS + 1], D = 0; static int G2 = 0; static int err = 0; static uint64_t M1[HV][HV], M2[HV][HV]; static uint16_t (*first64)[LAGS], (*last64)[LAGS]; static uint64_t *segn; static int64_t inv30(int q) { for (int a = 1; a < q; a++) if ((30 * a) % q == 1) return a; return -1; } static int member_slow(uint64_t j, int ci) { static const int wq[4] = {7, 11, 13, 17}; uint64_t r = 30 * j + CLS[ci]; for (int k = 0; k < 4; k++) { uint64_t m = r % wq[k]; if (m == 0 || m == (uint64_t)(wq[k] - 2)) return 0; } return 1; } static void *worker(void *arg) { (void)arg; uint64_t *B[3]; for (int c = 0; c < 3; c++) B[c] = malloc(8 * (SEGW + EXTW)); uint64_t *lNg = calloc(MAXG + 1, 8), *lRg = calloc(MAXG + 1, 8), lK[MAXF][LAGS + 1]; int lG2 = 0; memset(lK, 0, sizeof lK); uint64_t (*lM1)[HV] = calloc(HV * HV, 8), (*lM2)[HV] = calloc(HV * HV, 8); for (;;) { uint64_t s = __sync_fetch_and_add(&nextseg, 1); if (s >= nseg) break; uint64_t w0 = s * SEGW, j0 = w0 * 64, jend = j0 + 64ULL * SEGW; if (jend > n) jend = n; uint64_t nw = SEGW + EXTW; for (int c = 0; c < 3; c++) { uint64_t po = w0 % PATW; for (uint64_t k = 0; k < nw; k++) { B[c][k] = pat[c][po]; if (++po == PATW) po = 0; } for (int t = 0; t < nstrike; t++) { int64_t q = sq[t]; for (int e = 0; e < 2; e++) { int64_t a = sres[c][t][e]; uint64_t first = j0 + (uint64_t)(((a - (int64_t)(j0 % q)) % q + q) % q); for (uint64_t j = first - j0; j < nw * 64; j += q) B[c][j >> 6] &= ~(1ULL << (j & 63)); } } } /* walk openers in r order; a gap starts at each origin opener (j0 <= j < jend) */ int64_t prev = -1; int prevorigin = 0, done = 0; uint64_t ng = 0; int prevg = -1, prev2g = -1; uint64_t hm[MAXF]; memset(hm, 0, sizeof hm); uint16_t ring[LAGS]; for (uint64_t k = 0; k < nw && !done; k++) { uint64_t u = B[0][k] | B[1][k] | B[2][k]; while (u && !done) { int b = __builtin_ctzll(u); u &= u - 1; uint64_t j = k * 64 + b; for (int c = 0; c < 3; c++) if ((B[c][k] >> b) & 1) { int64_t r = (int64_t)(30 * j + CLS[c]); if (prev >= 0 && prevorigin) { int g = (int)(r - prev); if (g > MAXG) { err = 1; g = MAXG; } lNg[g]++; if (g > lG2) lG2 = g; if (g == prevg) lRg[g]++; if (g % 6 || g / 6 >= HV) err = 4; else { if (prevg >= 0) lM1[prevg / 6][g / 6]++; if (prev2g >= 0) lM2[prev2g / 6][g / 6]++; } prev2g = prevg; prevg = g; if (ng < LAGS) first64[s][ng] = (uint16_t)g; ring[ng % LAGS] = (uint16_t)g; ng++; uint16_t kb = killb[g]; for (int f = 0; f < NF; f++) { if ((kb >> f) & 1) { uint64_t hmask = hm[f]; while (hmask) { int t = __builtin_ctzll(hmask); hmask &= hmask - 1; lK[f][t + 1]++; } hm[f] = (hm[f] << 1) | 1ULL; } else hm[f] <<= 1; } } prev = r; prevorigin = (j0 + j < jend); if (!prevorigin) { done = 1; break; } } } } if (!done) err = 2; if (ng < LAGS) err = 3; for (int i = 0; i < LAGS; i++) last64[s][i] = ring[(ng - LAGS + i) % LAGS]; /* oldest -> newest */ segn[s] = ng; if (s % 256 == 0) fprintf(stderr, "seg %llu/%llu\n", (unsigned long long)s, (unsigned long long)nseg); } pthread_mutex_lock(&mu); for (int g = 0; g <= MAXG; g++) { Ng[g] += lNg[g]; Rg[g] += lRg[g]; } for (int f = 0; f < NF; f++) for (int k = 1; k <= LAGS; k++) Kk[f][k] += lK[f][k]; for (int a = 0; a < HV; a++) for (int b = 0; b < HV; b++) { M1[a][b] += lM1[a][b]; M2[a][b] += lM2[a][b]; } if (lG2 > G2) G2 = lG2; pthread_mutex_unlock(&mu); return NULL; } int main(int argc, char **argv) { if (argc < 4) { fprintf(stderr, "usage: lagspec x threads p1,p2,...\n"); return 2; } X = atoi(argv[1]); NT = atoi(argv[2]); for (char *t = strtok(argv[3], ","); t && NF < MAXF; t = strtok(NULL, ",")) FP[NF++] = atoi(t); if (X < 17) return 2; for (int g = 0; g <= MAXG; g++) { uint16_t kb = 0; for (int f = 0; f < NF; f++) { int m = g % FP[f]; if (m == 0 || m == 2 || m == FP[f] - 2) kb |= (uint16_t)(1u << f); } killb[g] = kb; } n = 1; for (int q = 7; q <= X; q++) { int pr = 1; for (int d = 2; d * d <= q; d++) if (q % d == 0) pr = 0; if (pr) { n *= q; if (q >= 19) sq[nstrike++] = q; } } nwords = (n + 63) / 64; nseg = (nwords + SEGW - 1) / SEGW; first64 = calloc(nseg, sizeof *first64); last64 = calloc(nseg, sizeof *last64); segn = calloc(nseg, 8); for (int c = 0; c < 3; c++) { pat[c] = calloc(PATW, 8); for (uint64_t j = 0; j < 64ULL * PATW; j++) if (member_slow(j, c)) pat[c][j >> 6] |= 1ULL << (j & 63); for (int t = 0; t < nstrike; t++) { int64_t q = sq[t], iv = inv30((int)q); sres[c][t][0] = (((-(int64_t)CLS[c]) % q + q) % q) * iv % q; sres[c][t][1] = (((-(int64_t)CLS[c] - 2) % q + q) % q) * iv % q; } } fprintf(stderr, "x=%d n=%llu segments=%llu threads=%d folds=%d\n", X, (unsigned long long)n, (unsigned long long)nseg, NT, NF); pthread_t th[64]; for (int i = 0; i < NT; i++) pthread_create(&th[i], NULL, worker, NULL); for (int i = 0; i < NT; i++) pthread_join(th[i], NULL); if (err) { fprintf(stderr, "ERROR %d\n", err); return 1; } /* boundary pairs: last 64 gaps of segment s with first 64 gaps of segment s+1 (cyclic) */ for (uint64_t s = 0; s < nseg; s++) { uint64_t t = (s + 1) % nseg; for (int a = 0; a < LAGS; a++) for (int b = 0; b < LAGS; b++) { int lag = (LAGS - a) + b; if (lag > LAGS) continue; int ga = last64[s][a], gb = first64[t][b]; uint16_t both = killb[ga] & killb[gb]; for (int f = 0; f < NF; f++) if ((both >> f) & 1) Kk[f][lag]++; if (lag == 1 && ga == gb) Rg[ga]++; if (lag == 1) M1[ga / 6][gb / 6]++; if (lag == 2) M2[ga / 6][gb / 6]++; } } uint64_t minseg = ~0ULL; for (uint64_t s = 0; s < nseg; s++) { D += segn[s]; if (segn[s] < minseg) minseg = segn[s]; } printf("{\"x\": %d, \"P\": %llu, \"D\": %llu, \"G2\": %d, \"lags\": %d, \"segments\": %llu, \"min_segment_gaps\": %llu,\n", X, (unsigned long long)(30 * n), (unsigned long long)D, G2, LAGS, (unsigned long long)nseg, (unsigned long long)minseg); printf(" \"hist\": {"); int first = 1; for (int g = 1; g <= MAXG; g++) if (Ng[g]) { printf("%s\"%d\": %llu", first ? "" : ", ", g, (unsigned long long)Ng[g]); first = 0; } printf("},\n \"repeats\": {"); first = 1; for (int g = 1; g <= MAXG; g++) if (Ng[g]) { printf("%s\"%d\": %llu", first ? "" : ", ", g, (unsigned long long)Rg[g]); first = 0; } printf("}"); for (int L = 1; L <= 2; L++) { /* value pairs (g_i, g_{i+L}) over the cyclic word, as [g, g', count] */ printf(",\n \"pairs%d\": [", L); first = 1; for (int a = 0; a < HV; a++) for (int b = 0; b < HV; b++) { uint64_t v = L == 1 ? M1[a][b] : M2[a][b]; if (v) { printf("%s[%d, %d, %llu]", first ? "" : ", ", 6 * a, 6 * b, (unsigned long long)v); first = 0; } } printf("]"); } printf(",\n \"folds\": {"); for (int f = 0; f < NF; f++) { uint64_t m = 0; for (int g = 1; g <= MAXG; g++) if ((killb[g] >> f) & 1) m += Ng[g]; printf("%s\n \"%d\": {\"m\": %llu, \"K\": [", f ? "," : "", FP[f], (unsigned long long)m); for (int k = 1; k <= LAGS; k++) printf("%s%llu", k > 1 ? ", " : "", (unsigned long long)Kk[f][k]); printf("]}"); } printf("}}\n"); return 0; }