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
- nat_self_delimiting_code_fiveThe self-delimiting code of 5 (binary 101, least significant bit first 1,0,1) is true,true, true,false, true,true, false.
- nat_self_delimiting_code_lengthThe self-delimiting code of m has length twice the number of binary digits of m plus one.
- edge_order_code_top_twoThe order consisting of the single edge {1, 0} of the complete graph on two vertices is encoded as false (endpoint 0), then true, true,…
- stochastic_mst_instance_codeThe binary encoding of an instance (G, p) of stochastic MST identification, G a simple graph on vertices 0..n-1 and p a rational…
- stochastic_mst_instance_code_bot_zeroThe empty graph on zero vertices is encoded by the single bit false.
- edge_order_codeThe binary encoding of a querying order (a list of edges of a graph on vertices 0..n-1): the edges in order, each edge {i, j} written as…
- stochastic_mst_instance_code_top_twoThe single edge on two vertices with probability 1/2 is encoded as 1,1,0 (n = 2 in unary), 1 (the pair 0,1 is adjacent), 1,1,0 (numerator…
- nat_self_delimiting_code_zeroThe self-delimiting code of 0 is the single bit false.
Lean source view module on GitHub
def nat_self_delimiting_code (m : ℕ) : List Bool := (Nat.bits m).flatMap (fun b => [true, b]) ++ [false]