AFTD Auto-Formalizing Theoretical Domains

slow_exact_nim_predicted_grundy

def

The explicit Sprague-Grundy function value for a position x on k+1 piles in slow exact k-Nim: with truncated piles y = slow_exact_nim_truncate k x, sum S = ∑ y_i, residue s = S % (2k), and odd count o, it returns 0 if s = k - 1, 1 if s = 2k - 1, and for other residues with r = min(s, 2k - 2 - s), 0 if o ≤ r, 1 if o ≥ r + 4 or (o = r + 2 and y 0 is even), 2 if o = r + 2 and both y 0 and y 1 are odd, and 3 if o = r + 2 and y 0 is odd and y 1 is even.

Statement

noncomputable def slow_exact_nim_predicted_grundy (k : ℕ) (x : Fin (k + 1) → ℕ) : ℕ
Defined in
arXiv:2611.14546:207
Verified
16 Nov 2026
Axioms
none listed
Built on 1
  • slow_exact_nim_truncateThe truncated position obtained from x on k+1 piles in slow exact k-Nim by capping each pile size x_i at the truncation bound…
Used by 1

Read back from the Lean

slow_exact_nim_predicted_grundy is a function that takes a natural number $k$ and a sequence $x = (x_0, x_1, \dots, x_k)$ of $k + 1$ natural numbers (represented as x : Fin (k + 1) → ℕ), and returns a natural number in $\{0, 1, 2, 3\}$. It computes the following: 1. A truncation bound $M = \text{slow\_exact\_nim\_truncation\_bound}(k, x)$, defined as the infimum (in $\mathbb{N}$) of the set of values $\lfloor (\sum_{i < j} x_i) / (j - 1) \rfloor$ for $j \in \{2, \dots, k + 1\}$. 2. A truncated sequence $y$, where $y_i = \min(x_i, M)$ for each $i \in \{0, \dots, k\}$. 3. The sum $S = \sum_{i=0}^k y_i$. 4. The remainder $s = S \bmod (2k)$ (where $S \bmod 0 = S$). 5. The number $o$ of indices $i \in \{0, \dots, k\}$ such that $y_i$ is odd. 6. The predicted Grundy value is then: - $0$, if $s = k - 1$; - $1$, if $s \neq k - 1$ and $s = 2k - 1$; - Otherwise, letting $r = \min(s, 2k - 2 - s)$ (with natural subtraction): - $0$, if $o \le r$; - $1$, if $o \ge r + 4$; - $1$, if $o = r + 2$ and $y_0$ is even; - $2$, if $o = r + 2$, $y_0$ is odd, and $y_1$ is odd; - $3$, if $o = r + 2$, $y_0$ is odd, and $y_1$ is even; - $0$, otherwise.

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 explicit Sprague-Grundy formula for slow exact k-Nim with k+1 piles from Theorem 1. -/
noncomputable def slow_exact_nim_predicted_grundy (k : ℕ) (x : Fin (k + 1) → ℕ) : ℕ :=
  let y := slow_exact_nim_truncate k x
  let S := ∑ i : Fin (k + 1), y i
  let s := S % (2 * k)
  let o := (Finset.univ.filter (fun i : Fin (k + 1) => Odd (y i))).card
  if s = k - 1 then 0
  else if s = 2 * k - 1 then 1
  else
    let r := min s (2 * k - 2 - s)
    if o ≤ r then 0
    else if r + 4 ≤ o then 1
    else if o = r + 2 ∧ Even (y 0) then 1
    else if o = r + 2 ∧ Odd (y 0) ∧ Odd (y 1) then 2
    else if o = r + 2 ∧ Odd (y 0) ∧ Even (y 1) then 3
    else 0
See it in the graphDiscuss this resultChallenge it