A natural-number coding of finite sequences

Write $\mathrm{bin}(n)$ for the canonical binary numeral of $n$, with $\mathrm{bin}(0)=0$. For a binary word $w$, let $c(w):=1^{\mathrm{\mid }w\mathrm{\mid }}0w\mathrm{.}$

For a finite sequence of natural numbers $a=(a_0,\dots ,a_{k-1}),$ define its sequence word $W(a):=11^{k}0c(\mathrm{bin}(a_0))\cdots c(\mathrm{bin}(a_{k-1}))\mathrm{.}$ The leading $1$ keeps the whole word a canonical positive binary numeral even when $k=0$.

The natural-number code of $a$ is the unique natural number $<mi\; mathvariant="normal">⌜</mi>a{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}}$ whose binary numeral is $W(a)$. In particular, the empty sequence has code $<mi\; mathvariant="normal">⌜</mi>(){<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}}=2$, because $W(())=10$.

By Finite tuples admit effective prefix-free binary encodings, the tuple of binary numerals inside $W(a)$ is effectively and uniquely decodable, so this construction gives an injective coding of finite sequences of natural numbers by natural numbers.

• Later items write $\mathrm{len}(s)$ for the decoded length of the sequence coded by $s$, and $(s{)}_i$ for its $i$th decoded entry when $i<\mathrm{len}(s)$.

• The coding is chosen so that the length header and every coordinate block can be recovered by bounded scans through the binary numeral of the code.