seeded_subtraction_seq
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
- seeded_subtraction_seq_initialThe value of the seeded subtraction sequence at any index $i < 2a + 1$ is equal to the corresponding seed value $\text{seed}(i)$.
- seeded_subtraction_seq_eventually_periodicFor every integer $a \ge 1$ and every binary initial seed of length $2a + 1$, the generated subtraction sequence is eventually periodic.
- seeded_subtraction_period_divisibility_case_oneFor parameter $a = 1$, every binary seed of length 3 generates a subtraction sequence whose least eventual period is 4, which divides…
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