# Extreme Exam V7-A 完整解答：Inverse-Bracelets 逆序取逆的原始環 > 本文件為完全自足之解答：答案、完整證明、精確計數方法、整數除法與取模的正當性論證、小规模交叉檢查、完整可重現程式（附錄 A–E）與逐項計算證書（附錄 F）。全文僅使用精確整數運算，無任何浮點、搜尋或未決求解器結果。 ## 0. 答案 ```json {"residue": 385583993536} ``` $$r = 385583993536$$ 其中 $N = 2\cdot 3^{11}\cdot 5^{7}\cdot 7^{5}\cdot 11^{3}\cdot 13^{2} = 104642664162129843750$，$M = 10^{12}$。 --- ## 1. 記號 - $G=S_3$，乘法 $(ab)(j)=a(b(j))$。字母集合 $L = G\setminus\{e\}$，$|L|=5$。 - 共軛類：$T$（3 個對換，序 2，self-inverse）、$C_3$（2 個三元環，序 3）。 - 字串 $w=(w_0,\dots,w_{N-1})$，索引模 $N$；**錨定乘積** $P(w)=w_0w_1\cdots w_{N-1}$。 - 合格字串：循環相異（$w_i\ne w_{i+1}$ 含首尾）、$P(w)=e$、最小週期恰為 $N$。 - 對 $d\mid N$ 記 $m=N/d$。$\mu$ 為 Möbius 函數。對 $d=1$：長度 1 的塊因首尾邊 $c_0\ne c_0$ 不可行，一切計數為 $0$（下表與程式皆如此處理）。 ## 2. 等價操作構成階為 $2N$ 的二面體群 定義 $R_k(w)_i = w_{i+k}$，$S_k(w)_i = (w_{k-i})^{-1}$。注意 $S_k = R_k\circ S_0$，且 $$S_0^2(w)_i = \big((w_{-i})^{-1}\big)^{-1} = w_i,\qquad S_0R_kS_0 = R_{-k},$$ 故 $\{R_k, R_kS_0: 0\le k **整數性**：$O(N)$ 是軌道數，右端必為整數（Burnside）。程式中另以斷言驗證 $X:=P+T_{ref}\equiv 0 \pmod{2N}$（見 §6）。 ## 4. $A(d,m)$：按乘積共軛類分解 $$A(d,m)=t_e(d)+[2|m]\,t_T(d)+[3|m]\,t_{C_3}(d),\qquad t_\chi(d)=\#\{c:\text{循環相異},\ P_c\in\chi\},$$ 因 $P_c^m=e\iff \mathrm{ord}(P_c)\mid m$，而 $S_3$ 元素序只由共軛類決定（$1,2,3$）。 計算 $t_\chi(d)$ 用了三種獨立方法，全部互驗一致（對 $d\le 8$ 並對 $5^d$ 個塊直接暴力枚舉；對随机大 $d<10^5$ 與大 $N$ 之全部實際 $d$ 逐項互驗）： **(V) 30 狀態转移**：狀態 $(a,p)$：當前字母 $a\in L$、已讀錨定乘積 $p\in S_3$；转移 $(a,p)\to(b,\;p\,b)$，$b\ne a$。起點 $(a,a)$ 對每個首字母 $a$；走 $d-1$ 步後對末字母 $b\ne a$（首尾邊）依 $p$ 的類累加。矩陣維度 $5\times 6=30$，冪次以 binary powering，$O(\log d)$ 次 $30\times30$ 整數矩陣乘。 **(GR) 群環 5×5 迹**：$M[a][b]=(a\ne b)\cdot e_b$（係數在群環 $\mathbb Z[S_3]$）。則 $(M^d)[a][a]$ 對 $a$ 求迹：路徑 $a=c_0\to c_1\to\cdots\to c_d=a$（每步字母改變，恰為循環邊條件），矩元為 $c_1c_2\cdots c_d$——每個塊以其末字母為對角指標計入恰一次。取 $P_c$ 之類即得 $t_\chi$。 **(CHAR) 特徵論閉式（附錄 B 用此獨立重算）**：對任意表示 $\rho$ 造 $M_\rho[a][b]=(a\ne b)\rho(b)$（維度 $5\dim\rho$ 的整數矩陣）。對角迹按上述路徑論證給 $$\mathrm{tr}\,M_\rho^{d} = \sum_\chi t_\chi\,\chi_\rho(\chi)\quad(\text{作為矩陣其迹即該值}).$$ 取平凡表示（$\chi=(1,1,1)$，$M_1=J_5-I$，特徵值 $4,-1^{\oplus4}$）、符号表示（$\chi=(1,-1,1)$）、與二維**整數**標準表示模型 $$s=(12)\mapsto\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad r=(123)\mapsto\begin{pmatrix}0&-1\\1&-1\end{pmatrix}$$ （$\chi_{\rm std}=(2,0,-1)$；模型的同態性在程式中以斷言核對全部 36 對乘積）。解 $3\times3$ 線性系統： $$E=t_e+t_T+t_{C_3}=4^d+4(-1)^d,\quad S=t_e-t_T+t_{C_3}=\mathrm{tr}\,M_s^d,\quad X=2t_e-t_{C_3}=\mathrm{tr}\,M_x^d,$$ $$t_e=\frac{E+S+2X}{6},\qquad t_{C_3}=2t_e-X,\qquad t_T=E-t_e-t_{C_3}.$$ 其中 $S,X$ 為固定 $5\times5$/$10\times10$ 整數矩陣冪之迹（整數可計算；等價於整線性遞推的封閉形式）。模運算下除以 6 以模 $6\cdot 2NM$ 的分子整除實現。 ## 5. $\beta_d(r,m)$：摺疊鏡像字 由移位引理只需三種軸型。鏡像 $i\mapsto r-i$ 在 $\mathbb{Z}/d$ 的不动點/不動邊結構由奇偶決定：$d$ 奇 ⟹ 對每個 $r$ 恰 1 不動點、1 不動邊；$d$ 偶、$r$ 奇 ⟹ 0 不動點、2 不動邊（$2i{+}1\equiv r$ 有 2 解）；$d$ 偶、$r$ 偶 ⟹ 2 不動點（$2i\equiv r$ 有 2 解，相距 $d/2$）、0 不動邊。以下 WLOG 取 $r=0$（偶軸）或 $r=1$（奇軸）。 ### (a) $d=2h+1$（所有 $r$） 不動點記 $x_0$，其鏡像值即自身：$x_0=x_0^{-1}\Rightarrow x_0\in T$。摺疊 $$c=(x_0,x_1,\dots,x_h,\ x_h^{-1},x_{h-1}^{-1},\dots,x_1^{-1}),\qquad |c|=1+2h=d .$$ 剩餘邊：鏈 $x_t\ne x_{t+1}$（$ti+s is a bijection # carrying S_r-fixed words to S_{r+2s}-fixed words and multiplies the anchored # product by conjugation, so beta depends on r only through parity (d even), # or not at all (d odd). WLOG r=0 (odd axes of even d: r=1): # d=2h+1: mirror vertex x_0 forced in T; middle edge forces x_h in C3; # word (x_0..x_h, x_h^{-1}..x_1^{-1}); product = x_0 exactly: # beta_odd = [2|m] * 1_T^T Adj^h 1_C3, Adj = J_5 - I ; C(d,m)=d*beta_odd # d=2h, r odd: two fixed edges => w_0=a in C3, w_1=a^{-1}, and x_h in C3; # word (a, a^{-1}, x_2..x_h, x_h^{-1}..x_2^{-1}); product = e ALWAYS; # chain x_2..x_h adj-diff, x_2 != a^{-1}: # beta_ro = 2 * 1_{All\{a^{-1}}}^T Adj^{h-2} 1_C3 (h=1: beta_ro = 2) # d=2h, r even: mirror vertices x_0,x_h in T; word (x_0..x_h, x_{h-1}^{-1}..x_1^{-1}); # product = x_0 B x_h B^{-1}, B = x_1..x_{h-1}; x_0,x_h in T makes the # inverse-edge constraints coincide with plain adjacency, so the chain # is merely adj-different; need ord(B^{-1} x_0 B x_h) | m. # DP state (x_t, y = B_t^{-1} x_0 B_t), y -> x'^{-1} y x'. # h=1: x_0,x_1 distinct transpositions, product in C3: 6*[3|m]. # beta_re; C(d,m) = (d/2)(beta_ro + beta_re) # # Final r: X = P+Tref computed mod 2N*M, exact division by 2N. # ============================================================ import sys, itertools from time import time # ---------------- S3 ---------------- PERMS=[(1,2,3),(2,1,3),(3,2,1),(1,3,2),(2,3,1),(3,1,2)] IDX={p:i for i,p in enumerate(PERMS)} def _c(a,b): return tuple(a[b[j]-1] for j in range(3)) # (ab)(j)=a(b(j)) MUL=[[IDX[_c(PERMS[a],PERMS[b])] for b in range(6)] for a in range(6)] INV=[next(q for q in range(6) if MUL[p][q]==0) for p in range(6)] CLS=[0,1,1,1,2,2] # 0=e 1=transposition 2=3-cycle (orders 1,2,3) LET=[1,2,3,4,5] # local letter -> group index T_LOC,C3_LOC=[0,1,2],[3,4] def divisors(n): small,big=[],[] i=1 while i*i<=n: if n%i==0: small.append(i) if i*i!=n: big.append(n//i) i+=1 return small+big[::-1] def mobius_terms(N): """[(d, m, mu(m))] for d|N, m=N/d squarefree""" pf=[];t=N;p=2 while p*p<=t: if t%p==0: pf.append(p) while t%p==0: t//=p p+=1 if t>1: pf.append(t) out=[] for mask in range(1<>i&1: m*=p;k+=1 out.append((N//m,m,(-1)**k)) return out # ---------------- modular linear algebra ---------------- def vv_mulrow(v,Me,mod): out=[0]*len(v) for i,a in enumerate(v): if a: for j,b in enumerate(Me[i]): if b: out[j]+=a*b if mod is not None: out=[x%mod for x in out] return out def m_mul(X,Y,mod): n=len(X) Ys=[[(j,b) for j,b in enumerate(Y[k]) if b] for k in range(n)] C=[[0]*n for _ in range(n)] for i in range(n): Ci=C[i] for k,a in enumerate(X[i]): if a: for j,b in Ys[k]: Ci[j]+=a*b if mod is not None: Ci[:]=[x%mod for x in Ci] return C def pows_of(base,jmax,mod): ps=[base] for _ in range(jmax-1): ps.append(m_mul(ps[-1],ps[-1],mod)) return ps def apply_pows(v,pows,e,mod): j=0 while e: if e&1: v=vv_mulrow(v,pows[j],mod) e>>=1; j+=1 return v # ---------------- base matrices ---------------- def V_base(): # state (last letter a, running product p); append b!=a Mx=[[0]*30 for _ in range(30)] for a in range(5): for p in range(6): row=Mx[a*6+p] for b in range(5): if b!=a: row[b*6+MUL[p][LET[b]]]+=1 return Mx def ADJ_base(): return [[1 if i!=j else 0 for j in range(5)] for i in range(5)] def Y_base(): # beta_re: state (x_t,y); append x'!=x_t ; y -> x'^{-1} y x' Mx=[[0]*30 for _ in range(30)] for x in range(5): for y in range(6): for xp in range(5): if xp==x: continue Mx[x*6+y][xp*6+MUL[MUL[INV[xp+1]][y]][xp+1]]+=1 return Mx def gr_base(): M=[[[0]*6 for _ in range(5)] for _ in range(5)] for a in range(5): for b in range(5): if a!=b: M[a][b][LET[b]]=1 return M def gr_mul(X,Y,mod): Xs=[[[(g,x) for g,x in enumerate(X[i][k]) if x] for k in range(5)] for i in range(5)] Ys=[[[(g,y) for g,y in enumerate(Y[k][j]) if y] for j in range(5)] for k in range(5)] C=[[[0]*6 for _ in range(5)] for _ in range(5)] for i in range(5): for k in range(5): if not Xs[i][k]: continue for j in range(5): Cij=C[i][j] for g1,x in Xs[i][k]: for g2,y in Ys[k][j]: Cij[MUL[g1][g2]]+=x*y if mod is not None: for i in range(5): for j in range(5): C[i][j]=[v%mod for v in C[i][j]] return C class Engine: def __init__(self,maxexp,mod=None,build_gr=False): self.mod=mod jmax=max(maxexp.bit_length(),4)+1 self.Vp=pows_of(V_base(),jmax,mod) self.Ap=pows_of(ADJ_base(),jmax,mod) self.Yp=pows_of(Y_base(),jmax,mod) self.build_gr=build_gr if build_gr: ps=[gr_base()] for _ in range(jmax-1): ps.append(gr_mul(ps[-1],ps[-1],mod)) self.GRp=ps def _red(self,x): return x%self.mod if self.mod is not None else x # ---------- t_c(d) via V ---------- def tcls(self,d): if d==1: return [0,0,0] # wrap edge c0!=c0 impossible t=[0,0,0] for a in range(5): v=[0]*30; v[a*6+LET[a]]=1 w=apply_pows(v,self.Vp,d-1,self.mod) for b in range(5): if b==a: continue for p in range(6): val=w[b*6+p] if val: t[CLS[p]]+=val return [self._red(x) for x in t] # ---------- t_c(d) via group-ring 5x5 trace ---------- def tcls_GR(self,d): if d==1: return [0,0,0] # wrap edge impossible acc=None;j=0;E=d while E: if E&1: acc=[[row[:] for row in m] for m in self.GRp[j]] if acc is None else gr_mul(acc,self.GRp[j],self.mod) E>>=1;j+=1 t=[0,0,0] for a in range(5): for g in range(6): v=acc[a][a][g] if v: t[CLS[g]]+=v return [self._red(x) for x in t] def A(self,d,m,use_gr=False): t0,tT,t3=self.tcls_GR(d) if use_gr else self.tcls(d) return self._red(t0+(tT if m%2==0 else 0)+(t3 if m%3==0 else 0)) # ---------- reflections ---------- def beta_odd(self,d,m): """d=2h+1: [2|m] * 1_T^T Adj^h 1_C3""" if m%2: return 0 h=(d-1)//2 tot=0 for i in T_LOC: v=[0]*5; v[i]=1 r=apply_pows(v,self.Ap,h,self.mod) for j in C3_LOC: tot+=r[j] return self._red(tot) def beta_ro(self,d,m): r"""d=2h, r odd (fixed edges): w_0=a in C3, w_1=a^-1; folded block (a, a^-1, x_2..x_h, x_h^-1..x_2^-1): chain x_2..x_h adj-diff, x_h != a, wrap edge x_2 != a^-1. Product = e IDENTICALLY (any m). x_0,x_h in C3, inverse-edges only bite when an x_t is in T, where x=x^-1 and adjacency already forbids x_t = x_{t+1}^-1. beta_ro = 2 * 1_{V\{a^-1}}^T Adj^{h-2} 1_{V\{a}}, h>=2 ; h=1 -> 2""" h=d//2 if h==1: return self._red(2) a=LET[C3_LOC[0]] a_inv=INV[a] v=[0]*5 for l in range(5): if LET[l]!=a_inv: v[l]=1 r=apply_pows(v,self.Ap,h-2,self.mod) tot=sum(r[j] for j in C3_LOC) return self._red(2*tot) def beta_re(self,d,m): """d=2h, r even (fixed vertices 0,h): x0,xh in T, chain adj-diff, product = x0 B xh B^-1 (B=x1..x_{h-1}); need ord(B^-1 x0 B xh) | m. DP over (x_t, y_t = B_t^-1 x0 B_t). h=1: distinct transpositions, product in C3 -> 6*[3|m].""" h=d//2 if h==1: return self._red(6 if m%3==0 else 0) v=[0]*30 for x0l in T_LOC: x0=LET[x0l] for x1l in range(5): if x1l==x0l: continue x1=LET[x1l] v[x1l*6+MUL[MUL[INV[x1]][x0]][x1]]+=1 u=apply_pows(v,self.Yp,h-2,self.mod) tot=0 for s in range(30): c=u[s] if not c: continue xl,y=s//6,s%6 for hl in T_LOC: if hl==xl: continue cl=CLS[MUL[y][LET[hl]]] if cl==0 or (cl==1 and m%2==0) or (cl==2 and m%3==0): tot+=c return self._red(tot) def C(self,d,m): if d%2: return self._red(d*self.beta_odd(d,m)) return self._red((d//2)*(self.beta_ro(d,m)+self.beta_re(d,m))) # ---------- totals ---------- def P(self,N,use_gr=False): s=0 for d,m,u in mobius_terms(N): s+=u*self.A(d,m,use_gr) return self._red(s) def Tref(self,N): s=0 for d,m,u in mobius_terms(N): s+=u*(N//d)*self.C(d,m) return self._red(s) def X(self,N,use_gr=False): return self._red(self.P(N,use_gr)+self.Tref(N)) def O_exact(self,N): Xs=self.X(N) assert Xs%(2*N)==0,"Burnside divisibility failed" return Xs//(2*N) # ================= brute force ================= def power_p(p,m): r=0 for _ in range(m): r=MUL[r][p] return r def word_prod(w): p=0 for x in w: p=MUL[p][LET[x]] return p def brute_A(d,m): c=0 for tup in itertools.product(range(5),repeat=d): if any(tup[i]==tup[(i+1)%d] for i in range(d)): continue if power_p(word_prod(tup),m)==0: c+=1 return c def brute_beta(d,r,m): c=0 for tup in itertools.product(range(5),repeat=d): if any(tup[i]==tup[(i+1)%d] for i in range(d)): continue if any(LET[tup[(r-i)%d]]!=INV[LET[tup[i]]] for i in range(d)): continue if power_p(word_prod(tup),m)!=0: continue c+=1 return c def orbit_rep(w): n=len(w) best=None for k in range(n): rot=tuple(w[(i+k)%n] for i in range(n)) ref=tuple(INV[LET[w[(k-i)%n]]]-1 for i in range(n)) for cand in (rot,ref): if best is None or cand[[0,1],[1,0]], r=(123)->[[0,-1],[1,-1]] (asserted on all 36 products). E=t0+tT+t3=4^d+4(-1)^d, S=t0-tT+t3=tr M_s^d, X=2t0-t3=tr M_x^d. beta_odd (d=2h+1, any r): mirror forces w_0 in T; fold (x0..xh,xh^-1..x1^-1); middle edge x_h != x_h^-1 -> x_h in C3; product = x_0 exactly. Wrap edge = w_1 != x_0^{-1}=x_0 redundant. = [2|m]*walks_K5(T->C3,h) = [2|m]*6(4^h-(-1)^h)/5 beta_ro (d=2h, r odd): fixed edges -> (x0, x0^-1, x2..xh, xh^-1..x2^-1), x0,x_h in C3, x2 != x0^-1, product=e IDENTICALLY, wrap redundant. h=1: 2 ; h>=2: 2*walks(V\{x0^-1}->C3,h-2) = 2[(8(4^{h-2}-(-1)^{h-2}))/5+(-1)^{h-2}] beta_re (d=2h, r even): x0,x_h in T (mirror fixed vertices); own 45-state DP: (last, z in T) x15 + (last, g in G) x30 buckets; z=B^-1 x0 B, z->x'^-1 z x'; final x_h in T\{last}, weight [ord(z x_h)|m]. Closed form (verified vs DP): beta_re = Z_h + [3|m](W_h - Z_h), W_h=walks(3,3,3,h), Z_h = h*3*2^{h-1} (h>=2), Z_1 = 0. Residue: same r=(X mod 2NM)/(2N), plus a CRT variant computing r mod 2^12 and r mod 5^12 from separate moduli 2N*2^12, 2N*5^12 then CRT -- to cross-check the modular-pipeline arithmetic itself. """ import sys from time import time from solver import MUL, INV, CLS, LET, mobius_terms, brute_beta, Engine # ---------------- 2-dim integral standard rep ---------------- def mm2(A,B): return [[A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]], [A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]]] I2=[[1,0],[0,1]]; S12=[[0,1],[1,0]]; R=[[0,-1],[1,-1]] RHO=[None]*6 RHO[0]=I2; RHO[1]=S12; RHO[4]=R; RHO[5]=mm2(R,R) RHO[2]=mm2(R,S12); RHO[3]=mm2(RHO[5],S12) for a in range(6): for b in range(6): assert mm2(RHO[a],RHO[b])==RHO[MUL[a][b]], (a,b) EPS=[1,-1,-1,-1,1,1] # ---------------- dense matrix powers with cache ---------------- class MP: def __init__(self,base,emax,mod): self.mod=mod self.p=[base] while (1<>=1; j+=1 return v def mat_of(self,e): acc=None; j=0 while e: if e&1: acc=self.p[j] if acc is None else self.mul(acc,self.p[j]) e>>=1; j+=1 return acc def trpow(self,e): A=self.mat_of(e) if A is None: return len(self.p[0]) if self.mod is None else len(self.p[0])%self.mod s=sum(A[i][i] for i in range(len(self.p[0]))) return s if self.mod is None else s%self.mod def MS(): return [[0 if a==b else EPS[LET[b]] for b in range(5)] for a in range(5)] def MX(): M=[[0]*10 for _ in range(10)] for a in range(5): for b in range(5): if a==b: continue blk=RHO[LET[b]] for i in range(2): for j in range(2): M[2*a+i][2*b+j]=blk[i][j] return M def tspec(d,mpS,mpX,mod): if mod is None: E=pow(4,d)+4*(-1)**d S=mpS.trpow(d); X=mpX.trpow(d) num=E+S+2*X; assert num%6==0 t0=num//6 return t0, E-t0-(2*t0-X), 2*t0-X M6=6*mod E=(pow(4,d,M6)+4*(-1)**d)%M6 S=mpS.trpow(d); X=mpX.trpow(d) num=(E+S+2*X)%M6 assert num%6==0 t0=num//6 t3=(2*t0-X)%mod tT=(E-t0-t3)%mod return t0,tT,t3 # ---------------- walks on K5 (mod-safe) ---------------- def walks(ns,nt,ni,n,mod=None): if n==0: v=ni return v%mod if mod else v if mod is not None: M5=5*mod res=(pow(4,n,M5)-(-1)**n)%M5 assert res%5==0 v=res//5*ns*nt+(-1)**n*ni return v%mod num=pow(4,n)-(-1)**n assert num%5==0 return num//5*ns*nt+(-1)**n*ni # ---------------- beta_re 45-state DP ---------------- def U45(): TI={1:0,2:1,3:2} M=[[0]*45 for _ in range(45)] def conj(g,xg): return MUL[MUL[INV[xg]][g]][xg] for l in range(5): for ti,z in enumerate((1,2,3)): for x in range(5): if x==l: continue z2=conj(z,x+1) if z2 in TI: M[l*3+ti][x*3+TI[z2]]+=1 else: M[l*3+ti][15+x*6+z2]+=1 for l in range(5): for g in range(6): for x in range(5): if x==l: continue g2=g if CLS[g]==0 else conj(g,x+1) M[15+l*6+g][15+x*6+g2]+=1 return M def beta_re_dp(h,m,mp,exact_mod=None): """mp: MP for U45 with target mod (or None exact small).""" if h==1: v=6 if m%3==0 else 0 return v%(exact_mod if exact_mod else 10**130) TI={1:0,2:1,3:2} v=[0]*45 for x0 in (1,2,3): for x1 in range(5): if LET[x1]==x0: continue z=MUL[MUL[INV[LET[x1]]][x0]][LET[x1]] v[x1*3+TI[z] if z in TI else 15+x1*6+z]+=1 u=mp.apply_row(v,h-2) tot=0 for l in range(5): for ti,z in enumerate((1,2,3)): c=u[l*3+ti] if not c: continue for hg in (1,2,3): if hg-1==l: continue pr=CLS[MUL[z][hg]] if pr==0 or (pr==1 and m%2==0) or (pr==2 and m%3==0): tot+=c for g in range(6): c=u[15+l*6+g] if not c: continue for hg in (1,2,3): if hg-1==l: continue pr=CLS[MUL[g][hg]] if pr==0 or (pr==1 and m%2==0) or (pr==2 and m%3==0): tot+=c mod=mp.mod return tot%mod if mod is not None else tot # ---------------- cross checks ---------------- def cross(): ok=True; import random random.seed(5) eng=Engine(800) mpS=MP(MS(),800,None); mpX=MP(MX(),800,None) for d in list(range(1,26))+[random.randrange(26,600) for _ in range(6)]: te=eng.tcls(d); ts=tspec(d,mpS,mpX,None) if list(ts)!=te: ok=False; print(f"FAIL tspec d={d}: {ts} vs {te}") for d in list(range(3,30,2))+[random.randrange(3,900)|1]: h=(d-1)//2 b2=6*((pow(4,h)-(-1)**h)//5) if eng.beta_odd(d,2)!=b2: ok=False; print(f"FAIL bodd d={d}") for d in list(range(4,30,2))+[(random.randrange(3,900)|1)*2]: h=d//2 c=2*walks(4,2,1,h-2) if eng.beta_ro(d,1)!=c: ok=False; print(f"FAIL bro d={d}") mpU=MP(U45(),30,None) for h in list(range(1,13))+[random.randrange(13,500) for _ in range(6)]: mpU_e=mpU if h<=30 else MP(U45(),2*h,10**60) for m in (1,2,3,6): dp=beta_re_dp(h,m,mpU_e) if dp>=10**60: dp%=10**60 # exact closed form, proved: z=B^-1 x0 B is ALWAYS a transposition # (conjugacy), so product z*xh has class e (z=xh) or C3 (z!=xh): # beta_re = Z_h + [3|m](W_h - Z_h), # Z_h = (12/5)(4^{h-1}+(-1)^h) (=0 at h=1), # W_h = walks(3,3,3,h) = 9(4^h-(-1)^h)/5 + 3(-1)^h. Z=(12*(pow(4,h-1)+(-1)**h))//5 W=walks(3,3,3,h) cl=Z+((W-Z) if m%3==0 else 0) if mpU_e.mod is not None: cl%=mpU_e.mod if dp!=cl: ok=False; print(f"FAIL bre closed h={h} m={m}: dp={dp} cl={cl}") en=eng.beta_re(2*h,m) if mpU_e.mod is not None: en%=mpU_e.mod if dp!=en: ok=False; print(f"FAIL bre eng h={h} m={m}: dp={dp} en={en}") if 2*h<=8: bb=brute_beta(2*h,0,m) if dp!=bb: ok=False; print(f"FAIL bre brute h={h} m={m}: dp={dp} brute={bb}") print("path4 cross-checks:","PASS" if ok else "FAIL") return ok # ---------------- full X and residue ---------------- def X_mod(N,mod): emax=N mpS=MP(MS(),emax,6*mod); mpX=MP(MX(),emax,6*mod) mpU=MP(U45(),emax,mod) P=0;Tr=0 for d,m,mu_ in mobius_terms(N): t0,tT,t3=tspec(d,mpS,mpX,mod) A=(t0+(tT if m%2==0 else 0)+(t3 if m%3==0 else 0))%mod P=(P+mu_*A)%mod if d%2: h=(d-1)//2 if m%2: Cc=0 else: Cc=(d%mod)*walks(3,2,0,h,mod)%mod*6%mod if False else (d%mod)*(6*(((pow(4,h,5*mod)-(-1)**h)%(5*mod))//5)%mod)%mod else: h=d//2 bro=2 if h==1 else (2*walks(4,2,1,h-2,mod))%mod b=beta_re_dp(h,m,mpU) Cc=((d//2)%mod)*((bro+b)%mod)%mod Tr=(Tr+(mu_*(N//d))%mod*Cc)%mod return (P+Tr)%mod def r_full(): N=2*3**11*5**7*7**5*11**3*13**2 assert N==104642664162129843750 M=10**12 mod=2*N*M X=X_mod(N,mod) assert X%(2*N)==0,"path4 divisibility" return X//(2*N) def r_crt(): """independent modular-pipeline variant: r mod q^12 for q in {2,5}, CRT.""" N=2*3**11*5**7*7**5*11**3*13**2 parts={} for q in (2,5): pk=q**12 Xq=X_mod(N,2*N*pk) assert Xq%(2*N)==0 parts[q]=(Xq//(2*N))%pk # CRT r ≡ a2 mod 2^12, a5 mod 5^12 m2,m5=2**12,5**12 a2,a5=parts[2],parts[5] inv=pow(2**12,-1,5**12) r=(a2+(m2*((a5-a2)*inv % m5)))%(m2*m5) return r if __name__=='__main__': if 'cross' in sys.argv: cross() else: t=time(); r4=r_full() print(f"path4 r = {r4} ({time()-t:.1f}s)",flush=True) t=time(); rc=r_crt() print(f"path4 r (CRT pipeline) = {rc} ({time()-t:.1f}s)",flush=True) ans=open('answer.txt').read().strip() print("answer.txt:",ans,"->","MATCH" if str(r4)==ans and str(rc)==ans else "MISMATCH") ``` # 附錄 C：`fold_model.py`（§5 摺疊模型之獨立暴力核對） ```python #!/usr/bin/env python3 """Folded-block model for S_r-fixed words (letters = non-identity of S3), derived by hand and cross-checked with brute force: d=2h+1, any r: fold (x_0..x_h, x_h^{-1}..x_1^{-1}): x_0 in T (mirror vertex), x_h in C3 (middle edge), chain adj-diff, wrap x_1 != x_0 redundant (x_0=x_0^{-1}), product = x_0. d=2h, r odd: fixed edge {0,1}: w_0=a, w_1=a^{-1}; fold (a, a^{-1}, x_2..x_h, x_h^{-1}..x_2^{-1}): x_h in C3 (edge h vs h+1), x_2 != a^{-1}, chain x_2..x_h adj-diff, wrap edge (x_h,a) redundant. Product identically e. d=2h, r even: (x_0..x_h, x_{h-1}^{-1}..x_1^{-1}), x_0,x_h in T, chain adj-diff, wrap x_1 != x_0 (x_0 self-inverse); product = x_0 * B * x_h * B^{-1}, B=x_1..x_{h-1}.""" import sys, itertools sys.path.insert(0,'.') from solver import MUL, INV, LET, CLS, brute_beta, ADJ_base def vv(M,v,n): return [sum(M[i][j]*v[i] for i in range(n)) for j in range(n)] def powapply(M,base_rows,e,n): v=list(base_rows) Ml=[M] while (1<>=1; j+=1 return v def model_beta(d,r,m): if d%2: h=(d-1)//2 if m%2: return 0 # x0 in T -> x_h in C3 via adj^h tot=0 for x0 in (1,2,3): v=[0]*5; v[x0-1]=1 w=powapply(ADJ_base(),v,h,5) tot+=w[3]+w[4] return tot h=d//2 if r%2: if h==1: return 2 tot=0 for a in (4,5): ex=a-1 # x_2 != a^{-1}; a^{-1} is the other C3 element = 8-a index trick ainv = INV[a] # group idx v=[0]*5 for l in range(5): if LET[l]!=ainv: v[l]=1 w=powapply(ADJ_base(),v,h-2,5) tot+=w[3]+w[4] return tot # r even: 30-state (x_t, y=B^-1 x0 B) if h==1: return 6 if m%3==0 else 0 v=[0]*30 for x0 in (1,2,3): for x1l in range(5): if LET[x1l]==x0: continue x1=LET[x1l] v[x1l*6+MUL[MUL[INV[x1]][x0]][x1]]+=1 M=[[0]*30 for _ in range(30)] for x in range(5): for y in range(6): for xp in range(5): if xp==x: continue M[x*6+y][xp*6+MUL[MUL[INV[xp+1]][y]][xp+1]]+=1 u=powapply(M,v,h-2,30) tot=0 for s in range(30): c=u[s] if not c: continue xl,y=s//6,s%6 for hg in (1,2,3): if hg-1==xl: continue pr=CLS[MUL[y][hg]] if pr==0 or (pr==1 and m%2==0) or (pr==2 and m%3==0): tot+=c return tot def main(): ok=True for d in range(1,9): for r in range(d): for m in (1,2,3,4,6): b=brute_beta(d,r,m); f=model_beta(d,r,m) if b!=f: ok=False; print(f"FAIL d={d} r={r} m={m}: brute={b} model={f}") print("folded-model brute check:","PASS" if ok else "FAIL") return ok if __name__=='__main__': main() ``` # 附錄 D：`perterm_check.py`（大 $N$ 全部 64 項雙框架逐項互驗） ```python #!/usr/bin/env python3 """Per-term double computation of the 64 mu-terms for the big N: Engine (transfer matrices, solver.py) vs path4 (character theory + K5 walk formulas + 45-state DP). Compares A(d,m) and C(d,m) mod 2NM for every term, then recombines both ways and recomputes r.""" from time import time import solver, path4 from solver import Engine, mobius_terms, MUL, INV, CLS, LET N=2*3**11*5**7*7**5*11**3*13**2 M=10**12 MOD=2*N*M t0=time() eng=Engine(N,MOD) mpS=path4.MP(path4.MS(),N,6*MOD) mpX=path4.MP(path4.MX(),N,6*MOD) mpU=path4.MP(path4.U45(),N,MOD) def walks(m_,n_,i_,n__): return path4.walks(m_,n_,i_,n__,MOD) def A4(d,m): t0_,tT,t3=path4.tspec(d,mpS,mpX,MOD) return (t0_+(tT if m%2==0 else 0)+(t3 if m%3==0 else 0))%MOD def C4(d,m): if d%2: if m%2: return 0 h=(d-1)//2 return (d%MOD)*walks(3,2,0,h)%MOD # walks already has |T||C3|=6 factor h=d//2 bro=2 if h==1 else (2*walks(4,2,1,h-2))%MOD # Z_h = 12*(4^{h-1}+(-1)^h)/5 ; the numerator IS divisible by 5 since # 4^{h-1} = (-1)^{h-1} mod 5. Lift the residue mod 5MOD to a multiple of 5. q=(pow(4,h-1,5*MOD)+(5*MOD+(-1)**h))%(5*MOD) while q%5: q+=5*MOD Z=12*(q//5)%MOD W=walks(3,3,3,h) b=(Z+((W-Z)%MOD if m%3==0 else 0))%MOD # also compare against DP: bdp=path4.beta_re_dp(h,m,mpU) assert b==bdp,("closed vs DP",h,m,b,bdp) return ((d//2)%MOD)*((bro+b)%MOD)%MOD ok=True; P1=0;T1=0;P2=0;T2=0 for d,m,mu_ in mobius_terms(N): a1,c1=eng.A(d,m),eng.C(d,m) a2,c2=A4(d,m),C4(d,m) if a1!=a2 or c1!=c2: ok=False; print(f"MISMATCH d={d} m={m}: A {a1} vs {a2}; C {c1} vs {c2}") P1=(P1+mu_*a1)%MOD; T1=(T1+mu_*(N//d)*c1)%MOD P2=(P2+mu_*a2)%MOD; T2=(T2+mu_*(N//d)*c2)%MOD print("per-term agreement:", "PASS" if ok else "FAIL") X1=(P1+T1)%MOD; X2=(P2+T2)%MOD assert X1==X2 and X1%(2*N)==0 print("r from engine :",X1//(2*N)) print("r from path4 :",X2//(2*N)) print(f"({time()-t0:.1f}s)") ``` # 附錄 E：`structural_audit.py`（Möbius 前結構審計） ```python #!/usr/bin/env python3 """Structural audit: for N=2..10 verify the two Burnside ingredients BEFORE Möbius inversion, by direct brute force over ALL valid words (not just primitive): V(N) := #{w: adj-diff cyclic, P(w)=e} =? sum_{d|N} A(d, N/d) F(N) := #{(w,k): S_k w = w} over valid w =? sum_{d|N} (N/d) C(d, N/d) and after inversion: Pprim(N) =? #{primitive valid w}, Tref =? sum over fixed (w,k) primitive.""" import sys, itertools sys.path.insert(0,'.') from solver import (Engine, LET, MUL, INV, divisors, brute_beta) def mu(n): if n==1: return 1 m,res,d=n,1,2 while d*d<=m: if m%d==0: m//=d if m%d==0: return 0 res=-res d+=1 if m>1: res=-res return res def brute_V_F(N): V=0; F=0; Vp=0; Fp=0 w=[0]*N divs=[d for d in divisors(N) if d