AFTD Auto-Formalizing Theoretical Domains

slow_exact_nim_grundy

def

The Sprague-Grundy value slow_exact_nim_grundy k n x of a position x : Fin n → ℕ in slow exact k-Nim on n piles is defined as slow_exact_nim_grundy_comp k n (∑ i : Fin n, x i) x.

Statement

def slow_exact_nim_grundy (k n : ℕ) (x : Fin n → ℕ) : ℕ
Defined in
arXiv:2611.14546, Section 1
Verified
14 Nov 2026
Axioms
none listed
Built on 1
  • slow_exact_nim_grundy_compFor natural numbers k and n, fuel : ℕ, and position x : Fin n → ℕ, the fuel-bounded Sprague-Grundy value slow_exact_nim_grundy_comp k n…
Used by 4

Read back from the Lean

The declaration defines a function slow_exact_nim_grundy (k n : ℕ) (x : Fin n → ℕ) : ℕ, which computes the Grundy value (Sprague-Grundy / nim-value) of a position x in a variant of Nim where in each turn, a player must choose exactly k heaps (out of n) that each have at least 1 token and remove 1 token from each chosen heap. The value is computed by calling the helper slow_exact_nim_grundy_comp k n (∑ i, x i) x, which performs fuel-bounded recursion using the total token count ∑ i, x i as the initial fuel. At each step with fuel fuel + 1, it computes the minimum excluded value (finset_mex) of the Grundy values of all reachable next states (followers) evaluated with fuel. When fuel reaches 0, it returns 0.

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

/-- The Sprague-Grundy value of a position in slow exact k-Nim on n piles. -/
def slow_exact_nim_grundy (k n : ℕ) (x : Fin n → ℕ) : ℕ := slow_exact_nim_grundy_comp k n (∑ i, x i) x
See it in the graphDiscuss this resultChallenge it