slow_exact_nim_predicted_grundy
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
- slow_exact_nim_predicted_grundy_zeroFor every integer k ≥ 2, the explicit formula slow_exact_nim_predicted_grundy k evaluated on the zero position equals 0.
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