A Variable-Length Gray Code for the Natural Numbers

The reflected binary Gray code arranges the fixed-length binary representations of the integers so that consecutive numbers differ in a single bit.

Its usefulness, however, is tied to a fixed word length $b$, which both caps the range of representable numbers at $2^{b}-1$ and wastes bits on small integers.

We introduce a \emph{variable-length Gray code} $\V$, a total function from the natural numbers to the set of all finite binary strings, obtained by taking the reflected Gray code of $n+1$, discarding its leading zeros, and deleting the single leading one.

We prove four properties of this construction.

First, $\V$ is a bijection between the natural numbers and $\Bits$, so it is a complete code that assigns exactly one codeword to every finite binary string, including the empty string.

Second, the Levenshtein (edit) distance between the codewords of two consecutive integers is always one; within a block of equal-length codewords the step is a single-bit substitution, and at each block boundary it is a single insertion.

Third, codeword length is monotone non-decreasing in the encoded number and equals $\lfloor \log_2 (n+1) \rfloor$.

Fourth, the transition from $(k-1)$-bit to $k$-bit codewords occurs exactly at $n=\sum_{i=0}^{k} 2^{i}=2^{k+1}-1$, where $\V(n)=1\,0^{k}$.

The code therefore realises a Hamiltonian enumeration of $\Bits$ under unit edit steps while retaining a near-optimal, self-adapting length profile.

We discuss its compression behaviour relative to fixed-length Gray codes and its application to the \emph{Isal*} family of instruction-set string encodings of graphs, hypergraphs, molecules and symbolic-regression expressions, in which the Levenshtein distance between encodings is used as a structural-similarity proxy.