"""Job #754: can the permutation null be reduced to the POSITIONS of the top-m gaps? The full null needs the whole gap word (D(37) = 2.18e11 gaps: 218 GB as bytes), which the record does not store. If every maximal k-gap window is anchored at one of the tile's m largest gaps, then under a uniform permutation the null is determined by the positions of those m gaps, and each draw costs O(m) instead of O(D) -- making a T37 null cheap. Exact test: for m in {20, 100, 1000}, compare A_k over ALL cyclic windows (true) against A_k over windows that contain >= 1 of the m largest gaps (anchored) on every tile where the word is in hand. """ import numpy as np LMAX = 8 def primes_upto(n): s = bytearray([1]) * (n + 1) s[0:2] = b"\x00\x00" for i in range(2, int(n ** 0.5) + 1): if s[i]: s[i * i::i] = b"\x00" * (((n - i * i) // i) + 1) return [i for i in range(n + 1) if s[i]] def build(x): ps = primes_upto(x) W = 1 for p in ps: W *= p mask = np.zeros(W + 1, dtype=bool) for p in ps: for r in (0, p - 2): first = p if r == 0 else r if first <= W: mask[first::p] = True slots = np.flatnonzero(~mask[1:]).astype(np.int64) + 1 gaps = np.empty(slots.size, dtype=np.int64) gaps[:-1] = np.diff(slots) gaps[-1] = slots[0] + W - slots[-1] return W, gaps def windows(gaps, k): n = gaps.size dbl = np.concatenate([gaps, gaps]) acc = np.zeros(n, dtype=np.int64) for j in range(k): acc = acc + dbl[j:j + n] return acc print(" x D m A_k true A_k anchored exact? (for all k = 1..%d)" % LMAX) for x in [13, 17, 19, 23]: W, gaps = build(x) D = gaps.size top = np.argsort(-gaps) for m in [20, 100, 1000]: anchor = np.zeros(D, dtype=bool) anchor[top[:m]] = True ok_all = True detail = [] for k in range(1, LMAX + 1): s = windows(gaps, k) true = int(s.max()) # a window of k consecutive gaps starting at i contains an anchor if any of i..i+k-1 is one hit = np.zeros(D, dtype=bool) for j in range(k): hit |= np.roll(anchor, -j) anch = int(s[hit].max()) if hit.any() else -1 detail.append((true, anch)) if anch != true: ok_all = False bad = [k for k, (t, a) in enumerate(detail, 1) if t != a] print(" %-5d %-10d %-6d %11d %-12s %-7s %s" % (x, D, m, detail[0][0], "n/a" if ok_all else "lower", "yes" if ok_all else "NO", "" if ok_all else "fails k=%s" % bad))