AFTD Auto-Formalizing Theoretical Domains

run_grundy_aux

def

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
See it in the graphDiscuss this resultChallenge it