|
|
EXAMPLE
|
Let us call A(n) the string of 0's and 1's given by applying the step "repeat and drop the last symbol" n times to A(0) = 01. Let B be the operation "drop the last symbol", e.g., B(01) = 0. Then A(n+1) = A(n) + B(A(n)) and A(n+m) = A(n) + ... B^m(A(n)). Then if A(n) contains a sequence of k consecutive 0's and no longer sequence, let p be the number of digits which follow after the end of the last occurrence of this sequence in A(n). In other words, B^p(A(n)) ends in a sequence of exactly k 0's. So A(n+p) = A(n) + ... + B^p(A(n)) also ends in a sequence of k 0's. Therefore A(n+p+1), since it concatenates A(n+p) with B(A(n+p)), which starts with a 0, contains a sequence of exactly k+1 0's. To see that no earlier sequence contains k+1 consecutive 0's, see that A(n) didn't. A new such sequence can only be formed by concatenating a prefix of A(n) with another prefix of A(n), which starts with only one 0. So such a prefix would have to end with n 0's. But by definition of p, no B^m(A(n)) for m < p ends with n 0's.
Now we can construct a(5). As can be easily checked, A(12) is made up of "01" + (2044 symbols) + "0000" + (2047 symbols). Therefore "00000" first appears in A(2047 + 12 + 1) = A(2060). The index of the last 0 is equal to the length of A(2059) = 2^2059 + 1. So the index of the first 0 is 2^2059 - 3.
|
