#!/usr/bin/env python3 """Repair the reflection-scan coverage defect for s=34 (K*(34)) and s=36 (K*(36)). Independent covering implementation (pure Python, gcd + division only). For a given s and window length L it evaluates the HIGH canonical component of the reflection-quotiented block scan that return #928's segments omitted: low = [0, floor((N-L-1)/2)] (count floor((N-L+1)/2)) high = [N-L, floor((2N-L-1)/2)] (count floor((L+1)/2)) where N = prod_{odd p <= s}(p-2) is the number of level-s slots in one block [0, P(s)#). #928's 8 segments covered the low component; the high component (count 15 for L=30 at s=34, count 17 for L=34 at s=36) was never searched. """ import sys from math import gcd def primes_le(n): ps = [] for k in range(2, n + 1): if all(k % d for d in range(2, int(k ** 0.5) + 1)): ps.append(k) return ps def is_slot(r, prim): for p in prim: if r % p == 0 or (r + 2) % p == 0: return False return True def coverable(positions, Q): """Exact phase-assignment cover search (mirrors the kstar reduction).""" m = len(positions) nq = len(Q) res = [[p % q for q in Q] for p in positions] FULL = (1 << m) - 1 kill = [] for j, q in enumerate(Q): km = {} for a in range(q): a2 = (a - 2) % q mask = 0 for i in range(m): if res[i][j] == a or res[i][j] == a2: mask |= (1 << i) km[a] = mask kill.append(km) uc = [[bin(kill[j][a]).count("1") for a in range(Q[j])] for j in range(nq)] nodes = [0] best = [None] * nq def dfs(cov, used): nodes[0] += 1 if cov == FULL: return True i = 0 while (cov >> i) & 1: i += 1 rem = m - bin(cov).count("1") cap = sum(max(uc[j]) for j in range(nq) if not (used >> j) & 1) if cap < rem: return False for j in range(nq): if (used >> j) & 1: continue c = res[i][j] for a in (c, (c + 2) % Q[j]): km_a = kill[j][a] m2 = cov | km_a if m2 == cov: continue S = m2 ^ cov for j2 in range(nq): for s in range(m): if (S >> s) & 1: r = res[s][j2] uc[j2][r] -= 1 uc[j2][(r + 2) % Q[j2]] -= 1 ok = dfs(m2, used | (1 << j)) for j2 in range(nq): for s in range(m): if (S >> s) & 1: r = res[s][j2] uc[j2][r] += 1 uc[j2][(r + 2) % Q[j2]] += 1 if ok: best[j] = a return True return False return dfs(0, 0), best, nodes[0] def collect_window(start, L, prim): """L consecutive level-s slots beginning at `start` (start must be a slot).""" win = [start] cur = start while len(win) < L: cur += 1 if is_slot(cur, prim): win.append(cur) assert all(is_slot(w, prim) for w in win) return win def validate_witness(start, L, prim, Q, label): win = collect_window(start, L, prim) ok, ph, nodes = coverable(win, Q) print(f"[witness {label}] start={start} L={L} coverable={ok} nodes={nodes} " f"first={win[0]} last={win[-1]} span={win[-1]-win[0]}") if not ok: print(" !! positive control FAILED") sys.exit(2) return ok def run(s, L): prim = primes_le(s) P = 1 for p in prim: P *= p N = 1 for p in prim: if p >= 3: N *= (p - 2) Q = [q for q in primes_le(2 * s) if q > s] n_high = (L + 1) // 2 n_low = (N - L + 1) // 2 print(f"--- s={s} L={L} : P(s)#={P} N={N} Q={Q} ---") print(f" low={n_low} high={n_high} total={(N+1)//2}") top_desc = [] k = 1 while len(top_desc) < L: if is_slot(P - k, prim): top_desc.append(P - k) k += 1 top_asc = list(reversed(top_desc)) # indices N-L .. N-1 first = [] r = 1 while len(first) < n_high - 1: if is_slot(r, prim): first.append(r) r += 1 ncov = 0 for t in range(n_high): win = top_asc[t:] + [P + s0 for s0 in first[:t]] assert len(win) == L, len(win) ok, ph, nodes = coverable(win, Q) idx = N - L + t if ok: ncov += 1 print(f" window start-index {idx}: COVERING (nodes={nodes}) first={win[0]}") else: print(f" window start-index {idx}: negative (nodes={nodes}) first={win[0]}") print(f" -> covering={ncov} negative={n_high-ncov} of {n_high} high windows") return ncov, N if __name__ == "__main__": prim34 = primes_le(34) Q34 = [q for q in primes_le(68) if q > 34] validate_witness(24531881117, 29, prim34, Q34, "s=34 L=29") n1, N = run(34, 30) prim36 = primes_le(36) Q36 = [q for q in primes_le(72) if q > 36] validate_witness(20283513461, 33, prim36, Q36, "s=36 L=33") n2, N2 = run(36, 34) print() if n1 == 0 and n2 == 0: print("RESULT: both defects repaired -> K*(34)=29 and K*(36)=33 restored exactly.") else: print(f"RESULT: covering window found (s34={n1}, s36={n2}) -> a K* value is larger.")