# 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}{cc}0\hfill & \u03f5\hfill \\ 1\hfill & 0\hfill \\ 2\hfill & 1\hfill \\ 3\hfill & 00\hfill \\ 4\hfill & 01\hfill \\ 5\hfill & 10\hfill \\ 6\hfill & 11\hfill \\ 7\hfill & 000\hfill \\ \mathrm{\dots}\hfill & \mathrm{\dots}\hfill \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 \mathrm{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 |