nat_mex_list
The minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
Statement
def nat_mex_list (l : List ℕ) : ℕ- Defined in
- scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md, Section 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 26
- spider_none_one_inward_one_outward_opts_mexFor r ≥ 2 and φ ≠ free, the mex of the explicit option list of the κ₁ configuration equals r.
- spider_gamma_rotate_three_short_legsFor any leg p, centre status and fuel, the value of (s;{p,1^in,1^out}) equals the value of (s;{1^in,1^out,p}): the leg p may be moved from…
- 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…
- spider_blocked_incoming_one_outwardFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
- spider_gamma_root_optionsThe option list of the root state S(1,2,z) at fuel N+1 (with z = m+1 and N ≥ 3) is the mex of 8 explicit "head" options together with the…
- spider_blocked_two_three_level_fiveAt level t = 5, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 11 is at most 7.
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- spider_mex_incoming_one_outwardThe minimum excluded value of the explicit options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2…
- spider_blocked_none_one_inward_one_outward_opts_eqFor r ≥ 2, φ ≠ free, and assuming the closed form for all smaller levels, the mex of the raw option list equals the mex of the explicit…
- spider_mex_two_leg_one_freeGiven an explicit options list where every element has parity k % 2, the minimum excluded value is 1 - k % 2 (which is 1 when k is even,…
- spider_mex_one_twoThe mex of the explicit closed-form option list of S(1,2,z) (8 head values plus the long block, after substituting all closed forms)…
- 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 α β.
- spider_gamma_swap_twoThe Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.
- nat_mex_list_eq_oneIf a list of naturals contains 0 but not 1, then its mex is 1.
- spider_blocked_none_one_inward_one_outwardFor the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
- spider_gamma_fuel_independentFor every fuel at least the total number of markable edges in L plus one, the value of spider_gamma does not depend on the fuel: it equals…
- spider_blocked_none_one_inward_one_outward_raw_opts_eqFor r ≥ 2 and φ ≠ free, the value of (none;{(1,inward),(1,outward),(r,φ)}) at fuel r+3 is the mex of the raw option list…
- nat_mex_list_not_mem_and_ltFor a list l of naturals, nat_mex_list l is not a member of l, and every natural number below nat_mex_list l is a member of l.
- nat_mex_list_eq_of_all_eq_bitFor any list of natural numbers whose elements all equal a single bit b ∈ {0, 1}, if the list is non-empty, its nat_mex_list is 1 - b.
- nat_mex_list_eq_zeroIf a list of naturals does not contain 0, then its mex (minimum excluded value) is 0.
- run_grundy_auxThe auxiliary Grundy value function for a run of length k with boundary conditions α and β in the Game of Arrows, computed by recursion up…
- run_grundy_zeroFor any boundary conditions α and β, a run of length 0 in the Game of Arrows has Grundy value 0.
- spider_blocked_two_three_level_five_optionsOne unfolding step of the recursion for the level-5 root state (none;{(5,inward),2^*,3^*}) at fuel n+1: the value is the mex of the list…
- nat_mex_list_append_commFor any two lists of natural numbers l1 and l2, nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
- spider_gamma_reversalFor every fuel, centre status s and leg list L, the value of the spider state (s;L) equals the value of the state obtained by exchanging…
- spider_mex_list_eq_of_not_mem_and_lt_memIf a natural number m is absent from a list l of naturals and every k < m is present in l, then the mex of l is m.
Read back from the Lean
The definition nat_mex_list takes a list of natural numbers l : List ℕ and returns a natural number ℕ. It is defined via an auxiliary recursive function loop (n : ℕ) (fuel : ℕ) : ℕ, initialized with n = 0 and fuel = l.length + 1. In each step:
- If fuel = 0, it returns n.
- If fuel = fuel' + 1, it checks whether n ∈ l:
- If n ∈ l, it recurses with loop (n + 1) fuel'.
- If n ∉ l, it returns n.
(Operationally, this computes the minimum excluded natural number, or mex, of the list l, since at least one value in $\{0, 1, \dots, l.length\}$ does not appear in l.)
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 value (mex) of a finite list of natural numbers. -/ def nat_mex_list (l : List ℕ) : ℕ := let rec loop (n : ℕ) (fuel : ℕ) : ℕ := match fuel with | 0 => n | fuel + 1 => if n ∈ l then loop (n + 1) fuel else n loop 0 (l.length + 1)