finset_mex
deforiginal
The minimum excluded natural number (mex) of a finite set of natural numbers s, defined as the smallest natural number not belonging to s.
Statement
def finset_mex (s : Finset ℕ) : ℕ- Related work
- folklore
- Verified
- 14 Nov 2026
- Axioms
- none listed
- Used by 2
- op_1600_slow_exact_nim_bounded_grundyIn the normal-play game of slow exact k-Nim on k+2 piles, for every integer k ≥ 3, the range of the Sprague-Grundy function is bounded:…
- 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…
Read back from the Lean
Definition of finset_mex: given a finite set of natural numbers s, finset_mex s is defined as the first element in the list List.range (s.card + 1) (i.e., the integers 0, 1, ..., s.card in increasing order) that does not belong to s, defaulting to 0 if no such element is found (which cannot happen by the pigeonhole principle). This computes the minimum excluded value (mex) of s.
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 minimum excluded natural number (mex) of a finite set of natural numbers. -/ def finset_mex (s : Finset ℕ) : ℕ := ((List.range (s.card + 1)).find? (fun x => ¬(x ∈ s))).getD 0