PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
natural numbers identified with binary strings (Definition)

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

\begin{displaymath} \begin{array}{ll} 0 & \epsilon \ 1 & 0 \ 2 & 1 \ 3 & 0... ... 5 & 10 \ 6 & 11 \ 7 & 000 \ \ldots & \ldots \end{array}\end{displaymath}
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$.



"natural numbers identified with binary strings" is owned by tromp.
(view preamble)

View style:


Cross-references: length, place, relation, bijection, lexicographic order, string, binary, natural number

This is version 4 of natural numbers identified with binary strings, born on 2003-07-01, modified 2006-10-07.
Object id is 4415, canonical name is NaturalNumbersIdentifiedWithBinaryStrings.
Accessed 1088 times total.

Classification:
AMS MSC68Q30 (Computer science :: Theory of computing :: Algorithmic information theory )

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)