General Formulas


In general, if we're handed a string of 0's and 1's, say , where each of the 's is either a 0 or a 1, then there are

shorter strings ahead of in the list, while there are

strings smaller than among the strings of length exactly . Thus, appears as entry number

on our "big list."

Return to Example 1



 


In order to determine which binary string lives at position number on the list, we begin by determining the length of the string at position .

In order to simplify this computation, let's first find an expression for the sum of successive powers of 2. Notice that if we set

then

In other words, we must have .

Now, given , we first trap it between two such expressions; that is, we find satisfying

or

(In other words, we find the base 2 logarithm of + 2). We know that is a string of length + 1.

Finally, the th entry on our list is the number

written as a binary string of length + 1.

Return to Example 1


Neal Carothers - carother@bgnet.bgsu.edu