# natural numbers identified with binary strings

It is convenient to identify a natural number $n$ with the $n$th binary string in lexicographic order:

 $\begin{array}[]{ll}0&\epsilon\\ 1&0\\ 2&1\\ 3&00\\ 4&01\\ 5&10\\ 6&11\\ 7&000\\ \ldots&\ldots\end{array}$

The more common binary notation for numbers fails to be a bijection because of leading zeroes. Yet, there is a close relation: the $n$th binary string is the result of stripping the leading 1 from the binary notation of $n+1$.

With this correspondence in place, we can talk about such things as the length $l(n)$ of a number $n$, which can be seen to equal $\lfloor\log(n+1)\rfloor$.

Title natural numbers identified with binary strings NaturalNumbersIdentifiedWithBinaryStrings 2013-03-22 13:43:44 2013-03-22 13:43:44 tromp (1913) tromp (1913) 7 tromp (1913) Definition msc 68Q30