AFTD Auto-Formalizing Theoretical Domains

pell_word

def

The word u_n = c_1 c_2 c_2 c_3 c_3 c_4 ⋯ c_(n-2) c_(n-1), i.e. the concatenation, over 1 ≤ i ≤ n-2, of the two-letter block c_i c_(i+1), subscripts taken mod 5.

Statement

def pell_word (n : ℕ) : List (Fin 5)
Source
step towards finitely_ambiguous_nfa_pell_lower_bound
Verified
19 Oct 2026
Axioms
none listed
Used by 4
  • pell_word_lengthThe word u_n = c_1c_2…c_(n-2)c_(n-1) has length 2(n-2).
  • pell_run_encard_eq_countThe set of accepting runs of u_n in A_n has encard equal to the number of runs from q_1 to q_n.
  • pell_word_getThe j-th letter of u_n is c_(j/2+1) if j is even and c_(j/2+2) if j is odd.
  • pell_word_eq_prefixThe word u_n is the prefix v_(n-2) of the block-by-block sequence.

Lean source view module on GitHub

/-- The word of length 2(n-2) on which A_n has 2·P(n-2) accepting runs. -/
def pell_word (n : ℕ) : List (Fin 5) := ((List.range (n - 2)).map (· + 1)).flatMap (fun i =>
    [⟨i % 5, Nat.mod_lt _ (by decide)⟩, ⟨(i + 1) % 5, Nat.mod_lt _ (by decide)⟩])
See it in the graphDiscuss this resultChallenge it