run_grundy_aux
The auxiliary Grundy value function for a run of length k with boundary conditions α and β in the Game of Arrows, computed by recursion up to depth bound n using the minimum excluded value of reachable options.
Statement
def run_grundy_aux (n : ℕ) (k : ℕ) (α β : RunBoundary) : ℕ- Defined in
- scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md:417
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 3
- RunBoundaryThe boundary condition at an end of a path segment in the Game of Arrows is either free (denoted *), blocked inward (denoted →), or…
- run_move_legalIn a run of length k with boundary conditions α and β, orienting edge j in direction δ is legal if and only if (j ≠ 1 or α ∈ {free, δ})…
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- Used by 4
- run_grundy_stepFor every k > 0 and boundary conditions α and β, the Grundy value run_grundy k α β is the minimum excluded value of the nim-sums of the…
- run_grundy_aux_eq_run_grundyFor any natural numbers n and k with k + 1 ≤ n, and any boundary conditions α and β, run_grundy_aux n k α β equals run_grundy k α β.
- run_grundyThe Grundy value of a run of length k with boundary conditions α and β in the Game of Arrows, defined using depth bound k + 1.
- run_grundy_zeroFor any boundary conditions α and β, a run of length 0 in the Game of Arrows has Grundy value 0.
Read back from the Lean
run_grundy_aux is a recursively defined function that takes a recursion bound (fuel) n : ℕ, a length k : ℕ, and two boundary states α, β : RunBoundary, and computes a natural number (a Grundy/nim-value):
- If n = 0, it returns 0.
- If n is of the form n' + 1:
- If k = 0, it returns 0.
- If k ≠ 0, it considers all positions j = idx + 1 for idx ∈ {0, …, k - 1} (so j ∈ {1, …, k}) and all boundary choices δ ∈ {RunBoundary.blocked_in, RunBoundary.blocked_out}.
For each pair (j, δ), if the move is legal according to run_move_legal k α β j δ, it records the bitwise XOR (^^^) of run_grundy_aux n' (j - 1) α δ and run_grundy_aux n' (k - j) δ β.
Finally, it returns the minimum excluded natural number (mex) of this list of values, computed via nat_mex_list.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Recursive auxiliary function computing the Grundy value of a run of length k with boundary conditions α and β up to depth bound n. -/ def run_grundy_aux (n : ℕ) (k : ℕ) (α β : RunBoundary) : ℕ := match n with | 0 => 0 | n + 1 => if k = 0 then 0 else let opts : List ℕ := (List.range k).flatMap fun idx => let j := idx + 1 [RunBoundary.blocked_in, RunBoundary.blocked_out].filterMap fun δ => if run_move_legal k α β j δ then some (run_grundy_aux n (j - 1) α δ ^^^ run_grundy_aux n (k - j) δ β) else none nat_mex_list opts