# Extreme Exam V7-A — Solution ## Answer ```json {"residue": 385583993536} ``` with ``` N = 2·3^11·5^7·7^5·11^3·13^2 = 104642664162129843750, M = 10^12, Q mod 2NM = 80697072683760985056985380000000, r = (Q mod 2NM)/(2N) = 385583993536. ``` All arithmetic is exact integer arithmetic (Python). The complete 64-term certificate (one row per squarefree e | N, with T, G, term values) is in `certificate.json`; the reproducible program is `solver.py` (run `python solver.py test` for the N=2..10 cross-checks, `python solver.py big` for the final residue — 49 s on a laptop). --- ## 1. The equivalence group Let A = G∖{e} (the 5 letters), Y_N = {w ∈ A^(Z/N): w_i ≠ w_{i+1} cyclically, w_0w_1⋯w_{N−1} = e}, and X_N ⊂ Y_N the primitive words. **D_N = ⟨R_k, S_k⟩ has order 2N.** With S := S_0, S² = id, and S R_k S(w)_i = S R_k(w_{−i}^{−1}) … = w_{i−k} = R_{−k}(w)_i, so S R_k S = R_{−k}: D_N is a dihedral group of order 2N, every element uniquely R_k or R_k S. (Any "dihedral-type" presentation R^N=S^N=1, SR_kS=R_{−k} gives the same quotient of the abstract ⟨R,S⟩ presentation.) **Both generators act on Y_N.** R clearly. For S: adjacency, w_i ≠ w_{i+1} ⟺ w_{k−i}^{−1} ≠ w_{k−i−1}^{−1} ✓; product: ∏_i S(w)_i (i ascending) = w_k^{−1} w_{k−1}^{−1}⋯w_{k−N+1}^{−1} = (w_{k−N+1}⋯w_{k−1}w_k)^{−1} = (a cyclic conjugate of w_0⋯w_{N−1})^{−1} = e ✓. Primitivity is preserved by any permutation of positions induced by R, S. Hence D_N acts on X_N, and the required count A(N) is the number of orbits. ## 2. Burnside + Möbius: the master identity For k ≠ 0 mod N, R_k fixes only non-primitive words, so on X_N: 2N·A(N) = Σ_{g∈D_N} |Fix_{X_N}(g)| = |X_N| + Σ_{k=0}^{N−1} |Fix_{X_N}(S_k)|. (1) For d | N write m = N/d and let Y_d := {blocks v ∈ A^d : v_i ≠ v_{i+1} cyclically (indices mod d), v_0⋯v_{d−1} ∈ … }. A word of Y_N has period dividing d iff it is the m-fold repetition of a block v ∈ A^d with **cyclic** adjacency and prod(v)^m = e. Define T(d,m) = #{v ∈ A^d : cyclic adjacency, prod(v)^m = e}, f_d(r) = #{v ∈ A^d : cyclic adjacency, prod(v)^m = e, S_r v = v}, S_r(v)_i = v_{r−i}^{−1} (mod d), G(d,m) = Σ_{r mod d} f_d(r). Since S_k acts on d-periodic words exactly as S_{k mod d}, each residue r occurs m times among k = 0..N−1, so Σ_k |Fix_{Y}(S_k)| over the period-|–d set equals m·G(d,m). Möbius inversion over the divisor lattice (primitive = exact period N): |X_N| = Σ_{d|N} μ(N/d) T(d, N/d), Σ_k |Fix_{X_N}(S_k)| = Σ_{d|N} μ(N/d) · (N/d) · G(d, N/d). Substituting in (1), with e := N/d (μ(N/d) = μ(e) nonzero only for squarefree e | rad N, exactly 64 rows for our N): **Q(N) := 2N·A(N) = Σ_{e | rad(N)} μ(e)·[ T(N/e, e) + e·G(N/e, e) ]** (2) This is a finite exact-integer identity; no analysis, no approximation. ## 3. Computing T(d,m) — transfer matrix States (a, p) ∈ A × S3 ("last letter, running product"); for letters a≠b put N30[(a,p)][(b,p·b)] = 1 (indices encode the state as 6a+p; products use the given non-commutative composition (ab)(j)=a(b(j))). A length-d block with cyclic adjacency and product q is counted by C_d(q) = Σ_{a≠b} (N30^{d−1})[(a,a)][(b,q)] (start state (a,a) = first letter a; end state forces last letter b ≠ a — the closing edge of the cycle). Then T(d,m) = Σ_{q: q^m = e} C_d(q), and in S3 the set {q : q^m = e} is {e} ∪ T3 (if 2|m) ∪ C3 (if 3|m), i.e. sizes 1/3/2 combinations. d = 1 gives 0 (a 1-block fails cyclic adjacency), matching brute force. Everything mod the single final modulus 2NM; matrix power by binary exponentiation (log2 d ≤ 67 squarings of a 30×30 matrix; 64 rows share exponents d = N/e, all ≈ N). ## 4. Computing G(d,m) — closed form for S_r-fixed blocks S_r v = v means v_i = v_{r−i}^{−1}: the block is a "palindrome up to inversion" with one or two mirror centers. Counting per r (f_d(r) is r-independent by translation, so G = d·f_d(0)): **(a) d odd.** One center is a letter i with v_i = v_i^{−1} ⟹ v_i = x ∈ T3; reading from the center the word is x, c_1, …, c_L, c_L^{−1}, …, c_1^{−1}, L = (d−1)/2. The product telescopes to x, so prod^m = e ⟺ m even (else f = 0). Cyclic adjacency at the wrap junction requires c_L ≠ c_L^{−1} ⟺ c_L ∈ C3 (an involution letter equals its own inverse → adjacent to itself → forbidden), and x ≠ c_1 (the junction x|c_1^{-1}… wrap). Interior edges: consecutive c's differ. Chain count from c_1 to c_L with different neighbours is (M5^{L−1})[c_1][c_L] with M5[a][b] = [a≠b] (identity matrix when L = 1, which correctly forces c_1 = c_L): O(d) = Σ_{x∈T3} Σ_{c_1 ≠ x} Σ_{c_L∈C3} (M5^{(d−3)/2})[c_1][c_L], G = d·O(d), 0 for m odd, 0 for d=1. d=1 has no valid block (adjacency), matching the code. **(b) d even.** Two centers. If r is odd, both centers fall between letters: the word is c_1, …, c_{d/2}, c_{d/2}^{−1}, …, c_1^{−1}: product = e automatically (so any m is allowed); both junctions between the mirrored halves force c_1, c_{d/2} ∈ C3, interior edges differ: B(d) = Σ_{c_1, c_2 ∈ C3} (M5^{d/2 − 1})[c_1][c_2] (d=2: M5^0 = I ⟹ B = 2 ✓). If r is even, both centers are letters, which must be involutions; the word is x, c_1, …, c_L, y, c_L^{−1}, …, c_1^{−1}, L = d/2 − 1, x, y ∈ T3, and the product is P = x U y U^{−1}, U = c_1⋯c_L. A product of two involutions of S3 is e or a 3-cycle (never an involution), so P^m = e ⟺ (x = U y U^{−1}) or (3 | m). Adjacency: x ≠ c_1 and y ∉ {c_L, c_L^{−1}}. Counting the admissible (x, y) per chain (c_1, …, c_L) with running product U: - if 3|m: (3 − [c_1∈T3])·(3 − [c_L∈T3]) pairs (y ranges over T3 minus the (at most one) involution in {c_L, c_L^{−1}}; x over T3 minus c_1 if c_1∈T3); - if 3∤m: y free of the {c_L, c_L^{−1}} obstruction and x := U y U^{−1}; admissible iff x ≠ c_1, i.e. y ≠ U^{−1} c_1 U — giving 3−[c_1∈T3] when c_L ∈ C3, and 2 − [c_1∈T3 and U^{−1}c_1U ≠ c_L] … (in code: for c_L∈T3: 1 if c_1∈T3 else 2 when U^{−1}c_1U ∉ {c_L}, else 2). Chain multiplicities are tallied by the same 30-state matrix: (#chains c_1..c_L with product U) = (N30^{L−1})[(c_1,c_1)][(c_L,U)] (L≥1); L = 0 (d=2): P = xy with x≠y forced ⟹ P a 3-cycle ⟹ A = 6 if 3|m else 0. Summing over the d/2 even and d/2 odd residues r: G = (d/2)·(A(d,m) + B(d)). These closed forms were **not** trusted: they were checked against exhaustive enumeration of every block v ∈ A^d (5^d ≤ 390625 words) for every level d | N' with N' ∈ {2,…,10}, comparing T(d,m) and G(d,m) value-by-value — all exact. ## 5. The final division modulo M Q = 2N·A with A ∈ Z. Working modulo 2NM: Q mod 2NM = 2N·A mod 2NM = 2N·(A mod M), which is the unique multiple of 2N in [0, 2NM); hence r = A mod M = (Q mod 2NM) / 2N (exact integer division). The program asserts divisibility. This is legitimate because (2) is an identity of integers: each term T, G is reduced mod 2NM before the μ-sum, and reduction mod 2NM commutes with the sum and with the final division step above. No division by non-invertible quantities occurs anywhere (we never divide mod 2N; we divide the representative that is *known* to be a multiple of 2N, over the integers). ## 6. Small-scale cross-check (N = 2..8 required; done through N = 10) Full brute force: enumerate all 5^{N'} words, test adjacency (cyclic), product = e, primitivity, then quotient by the orbit of {R_k, S_k} (canonical minimum). Independent of (2). Result (both methods identical, and every intermediate T/G also matched the exhaustive level counts): | N' | A(N') orbits (brute = formula) | |---|---| | 2 | 1 | | 3 | 3 | | 4 | 6 | | 5 | 15 | | 6 | 63 | | 7 | 195 | | 8 | 717 | | 9 | 2428 | | 10 | 8901 | Level-by-level certificate spot values (exhaustive block enumeration = closed form, all four fields agree), e.g. for N'=4 and N'=6: | level d | m | T(d,m) | G(d,m) | |---|---|---|---| | 2 | 2 | 14 | 2 | | 4 | 1 | 38 | 28 | | 2 | 3 | 8 | 8 | | 3 | 2 | 42 | 18 | | 6 | 1 | 716 | 150 | Sanity of (2) at N'=4: Q = [T(4,1)+G(4,1)] − [T(2,2)+2·G(2,2)] = 66 − 18 = 48 = 2·4·6 ✓. At N'=6: Q = (716+150) − (42+2·18) − (8+3·8) + 0 = 756 = 2·6·63 ✓. (Hand values: G(3,2) = 3·O(3) = 18 ✓, A(2,3) = 6, B(2)=2.) ## 7. Reproducing ``` python solver.py test # N'=2..10: brute orbits vs formula + per-level T,G vs exhaustive; prints ALL PASS python solver.py big # prints {"residue": 385583993536}; writes certificate.json python audit.py # re-derives r from certificate rows independently; hand closed-form checks ``` `certificate.json` lists all 64 (e, μ, d, T, G, term) rows mod 2NM plus Q and r, so the final answer can be re-summed without rerunning any matrix power. Files: `solver.py`, `certificate.json`, `big_result.json`, `small_tests.json`, `extra_tests.py`, `audit.py`, this document.