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
Canonical name	NaturalNumbersIdentifiedWithBinaryStrings
Date of creation	2013-03-22 13:43:44
Last modified on	2013-03-22 13:43:44
Owner	tromp (1913)
Last modified by	tromp (1913)
Numerical id	7
Author	tromp (1913)
Entry type	Definition
Classification	msc 68Q30