AFTD Auto-Formalizing Theoretical Domains

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