AFTD Auto-Formalizing Theoretical Domains

ocacagChain

def

The dyadic chain to leaf v: start at the top cut [1, 2^(k-1)] and bisect k-1 times toward v, giving k nested cuts down to the singleton {v}.

Statement

def ocacagChain (k : ℕ) (v : ℤ) : List (ℤ × ℤ)
Source
step towards online_cycle_augmentation_adversary_cost_ge
Verified
09 Nov 2026
Axioms
none listed
Built on 2
  • ocacagChainAuxThe list of nested dyadic cuts obtained by starting at interval c and bisecting t times toward the vertex v: [c] for t = 0, and c ::…
  • ocacagSplitBisect the integer interval c = [c.1, c.2] at its midpoint m = floor((c.1+c.2)/2), returning the half that contains v: [c.1, m] if v ≤ m,…

Lean source view module on GitHub

/-- The dyadic chain of cuts leading to the vertex `v`, starting from the top cut [1, 2^(k-1)]. -/
def ocacagChain (k : ℕ) (v : ℤ) : List (ℤ × ℤ) := ocacagChainAux (k - 1) (1, (2 : ℤ) ^ (k - 1)) v
See it in the graphDiscuss this resultChallenge it