sternDiatomic
def
Stern's diatomic sequence s(n) is defined by s(0) = 0, s(1) = 1, s(2m) = s(m), and s(2m+1) = s(m) + s(m+1) for m ≥ 1.
Statement
def sternDiatomic : ℕ → ℕ- Defined in
- scout/2611-01243-halving-partitions-and-hyperbinary-expansions.md:368
- Verified
- 03 Nov 2026
- Axioms
- none listed
Read back from the Lean
The definition of a function sternDiatomic : ℕ → ℕ defined by recursion on ℕ:
- sternDiatomic 0 = 0
- sternDiatomic 1 = 1
- For any natural number of the form n + 2 (i.e., any integer $m \ge 2$):
- if (n + 2) % 2 = 0 (i.e., $m$ is even), then sternDiatomic m = sternDiatomic (m / 2);
- otherwise (i.e., $m$ is odd), then sternDiatomic m = sternDiatomic (m / 2) + sternDiatomic (m / 2 + 1),
where division / is natural number division.
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
/-- Stern's diatomic sequence s(n). -/ def sternDiatomic : ℕ → ℕ | 0 => 0 | 1 => 1 | n + 2 => if h : (n + 2) % 2 = 0 then have : (n + 2) / 2 < n + 2 := Nat.div_lt_self (Nat.succ_pos (n + 1)) (by decide) sternDiatomic ((n + 2) / 2) else have : (n + 2) / 2 < n + 2 := Nat.div_lt_self (Nat.succ_pos (n + 1)) (by decide) have : (n + 2) / 2 + 1 < n + 2 := by omega sternDiatomic ((n + 2) / 2) + sternDiatomic ((n + 2) / 2 + 1) termination_by n => n