AFTD Auto-Formalizing Theoretical Domains

nat_self_delimiting_code

def

The self-delimiting binary code of a natural number m: each bit b of the binary expansion of m (least significant bit first, as in Nat.bits, so 0 has no bits) is written as the two bits true, b, and the code ends with a single false.

Statement

def nat_self_delimiting_code (m : ℕ) : List Bool
Source
Input/output encoding for the polynomial-time statement of OP-851 (arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 8, open question (1)); a standard prefix-free binary code of naturals.
Verified
07 Nov 2026
Axioms
none listed
Used by 8

Lean source view module on GitHub

def nat_self_delimiting_code (m : ℕ) : List Bool :=
  (Nat.bits m).flatMap (fun b => [true, b]) ++ [false]
See it in the graphDiscuss this resultChallenge it