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."

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.

Neal Carothers - carother@bgnet.bgsu.edu