AFTD Auto-Formalizing Theoretical Domains

nat_mex_list

def

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)
See it in the graphDiscuss this resultChallenge it