#!/usr/bin/env python3 """kstar_dfs.py -- K* by a pruned two-class covering search (job #2087, route 92). K*(P# -> P'#) = the longest run of consecutive level-P slots (cyclic, in the big tile of period P#*NCOPY) that some copy alignment kills entirely with the entering primes Q = (P, P'] (two classes 0 and -2 per prime). A window of k consecutive slots x_1..x_k is 'coverable' iff there exist residues (j mod q)_q such that every slot is killed by some q at its residue. That is decided EXACTLY by a dynamic programme over the covered-slot bitmask with two prunes: (i) capacity: the summed maximal kills of the remaining primes must reach the number of uncovered slots; (ii) reachable masks only. Monotonicity (a coverable window's sub-windows are coverable) lets the search extend from the current best length: each start i is tested at length best+1 first. The same DP, counting instead of deciding, gives N_k for a window as the number of alignments (CRT), which equals the inclusion-exclusion term of the pinned engine; --count k computes N_k over all starts for a check. Usage: kstar_dfs.py P PP [--count k] [--lo a --hi b] -> JSON on stdout, progress on stderr. """ import sys, math, json, time, argparse def primes_upto(n): return [q for q in range(2, n + 1) if all(q % d for d in range(2, int(q ** 0.5) + 1))] def slot_word(P): Ps = 1 for q in primes_upto(P): Ps *= q slots = [r for r in range(Ps) if math.gcd(r, Ps) == 1 and math.gcd(r + 2, Ps) == 1] return slots, Ps def window_positions(slots, Ps, D, i, k): # positions of slots i..i+k-1 in the big tile (ascending, wrapping into later copies) return [slots[(i + t) % D] + Ps * ((i + t) // D) for t in range(k)] def tables(pos, Q, Ps): """per prime: list of (kill mask) over residues j mod q (all q residues); killed iff (j*Ps + pos) mod q in {0, q-2}.""" tabs = []; caps = [] for q in Q: pm = Ps % q tab = [] best = 0 for j in range(q): base = (j * pm) % q m = 0 for t, u in enumerate(pos): r = (base + u) % q if r == 0 or r == q - 2: m |= 1 << t tab.append(m); c = bin(m).count('1'); best = max(best, c) tabs.append(tab); caps.append(best) return tabs, caps def coverable(pos, Q, Ps, count=False): k = len(pos); full = (1 << k) - 1 tabs, caps = tables(pos, Q, Ps) if sum(caps) < k: return 0 suffix = [0] * (len(Q) + 1) for a in range(len(Q) - 1, -1, -1): suffix[a] = suffix[a + 1] + caps[a] dp = {0: 1} for a, tab in enumerate(tabs): nd = {} rem = suffix[a + 1] for m, c in dp.items(): for km in tab: mm = m | km if k - bin(mm).count('1') > rem: continue nd[mm] = nd.get(mm, 0) + c dp = nd if not dp: return 0 return dp.get(full, 0) def kstar(P, PP, lo=0, hi=None, verbose=True): slots, Ps = slot_word(P); D = len(slots) Q = [q for q in primes_upto(PP) if q > P] hi = D if hi is None else hi best = 0; best_at = None; t0 = time.time(); tested = 0 for i in range(lo, hi): k = best + 1 while True: pos = window_positions(slots, Ps, D, i, k) tested += 1 if coverable(pos, Q, Ps): best = k; best_at = i; k += 1 else: break if verbose and i % 50000 == 0 and i: print(f"[progress] {P}#->{PP}# {i}/{D} best={best} tested={tested} {time.time()-t0:.0f}s", file=sys.stderr, flush=True) return dict(P=P, PP=PP, D=D, Q=Q, kstar=best, witness_start=best_at, windows_tested=tested, seconds=round(time.time() - t0, 1), lo=lo, hi=hi) def count_Nk(P, PP, k): slots, Ps = slot_word(P); D = len(slots) Q = [q for q in primes_upto(PP) if q > P] total = 0 for i in range(D): total += coverable(window_positions(slots, Ps, D, i, k), Q, Ps, count=True) return total if __name__ == '__main__': ap = argparse.ArgumentParser() ap.add_argument('P', type=int); ap.add_argument('PP', type=int) ap.add_argument('--count', type=int, default=None) ap.add_argument('--lo', type=int, default=0); ap.add_argument('--hi', type=int, default=None) a = ap.parse_args() if a.count: print(json.dumps(dict(P=a.P, PP=a.PP, k=a.count, N_k=count_Nk(a.P, a.PP, a.count)))) else: print(json.dumps(kstar(a.P, a.PP, a.lo, a.hi)))