PlanetMath: natural numbers identified with binary strings

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

natural numbers identified with binary strings

(Definition)

It is convenient to identify a natural number with the 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

th binary string is the result of stripping the leading 1 from the binary notation of

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

"natural numbers identified with binary strings" is owned by tromp.

(view preamble)

Log in to rate this entry.
(view current ratings)

Cross-references: length, place, relation, bijection, numbers, 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 1491 times total.

Classification:

AMS MSC:

68Q30 (Computer science :: Theory of computing :: Algorithmic information theory )

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact