AFTD Auto-Formalizing Theoretical Domains

seeded_subtraction_seq

def

The binary sequence defined recursively from a seed of length $2a + 1$, where the first $2a + 1$ values are given by the seed, and each subsequent value at index $n \ge 2a + 1$ is 1 if at least one of the values at $n - a$, $n - 2a$, or $n - (2a + 1)$ is 0, and 0 otherwise (with value false if $a = 0$).

Statement

def seeded_subtraction_seq (a : ℕ) (seed : Fin (2 * a + 1) → Bool) : ℕ → Bool
Defined in
knowledgebase, OP-1251
Verified
08 Nov 2026
Axioms
none listed
Used by 3

Read back from the Lean

seeded_subtraction_seq defines a function ℕ → Bool parameterized by a natural number a : ℕ and a seed function seed : Fin (2 * a + 1) → Bool. For any natural number n: - If n < 2 * a + 1, the function returns seed ⟨n, _⟩. - If n ≥ 2 * a + 1: - If a = 0, it returns false. - If a ≠ 0, it returns true if at least one of the values of seeded_subtraction_seq a seed at n - a, n - 2 * a, or n - (2 * a + 1) is false (i.e., !seq(n - a) || !seq(n - 2 * a) || !seq(n - (2 * a + 1))), and false if all three are true.

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 binary sequence generated by the subtraction game with moves {a, 2a, 2a+1} from an initial seed of length 2a+1. -/
def seeded_subtraction_seq (a : ℕ) (seed : Fin (2 * a + 1) → Bool) : ℕ → Bool
  | n =>
  if h : n < 2 * a + 1 then
    seed ⟨n, h⟩
  else
    if ha : a = 0 then false
    else
      have h1 : n - a < n := by omega
      have h2 : n - 2 * a < n := by omega
      have h3 : n - (2 * a + 1) < n := by omega
      !seeded_subtraction_seq a seed (n - a) ||
      !seeded_subtraction_seq a seed (n - 2 * a) ||
      !seeded_subtraction_seq a seed (n - (2 * a + 1))
termination_by n => n
See it in the graphDiscuss this resultChallenge it