The Kolakoski tree

Draw an infinite tree according to the following rules:

• Each tree node is labeled 1 or 2, and has a number of children equal to its label.
• If the nodes are placed into their breadth-first search ordering, then two consecutive nodes have the same label if and only if they have the same parent.

There are two choices for the root label, but the trees they produce are almost the same as each other, so let's say the root is labeled 2, giving the tree shown below together with its spiraling breadth first search order. (If the root were labeled 1, the only difference would be to add one more node labeled 1 above the node that is the root in the drawing.)

Then the breadth-first sequence of labels that we obtain is exactly the Kolakoski sequence, starting from its third term. The Kolakoski sequence begins 1,2,2,1,1,2,1,2,2,1,2,2... and has the property that it equals the sequence of run-lengths in itself: the numbers 1, 2, 2, etc. are exactly the numbers of consecutive 1's, 2's, 1's, etc. in the sequence. Our tree is defined in such a way that each run of consecutive equal labels comes from the same parent, so the run-lengths of the sequence equal the numbers of children of the nodes, which equal the labels of the nodes, which define the sequence itself.

The fact that this tree encodes the Kolakoski sequence in its breadth-first ordering is closely related to the fact that breadth first search on a tree can be encoded recursively as the following algorithm: first, output the root node. Then, for each node in a recursive breadth-first search, output its children. Applying this technique to the Kolakoski tree gives us the following Python recursive generator for the Kolakoski sequence itself:

def recurse():
    yield 2
    output = 1
    for x in recurse():
        for i in range(x):
            yield output
        output = 3 - output

def Kolakoski():
    yield 1
    yield 2
    for x in recurse():
        yield x

(The only reason we need two separate functions is to handle the first two terms in the sequence, the ones that are not part of the tree.) If this algorithm is used to generate the first \( n \) terms of the sequence, then it calls itself recursively \( O(\log n) \) levels deep, with each level of recursion tracking one level higher in the tree and generating approximately \( 2/3 \) as many values as its caller. Each level of recursion has only a constant amount of storage for its local variables. Therefore, it takes \( O(n) \) time and \( O(\log n) \) space to generate the whole sequence.

Something very similar to this algorithm, with the same analysis, is described in the paper "A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence", by Johan Nilsson in J. Integer Sequences 2012. But he replaces the chain of recursive calls by an explicit data structure, which makes the algorithm's description longer and I think more confusing. And instead of making a single tree from all but the first two numbers in the sequence, Nilsson uses a forest with infinitely many trees, with each level of the forest being labeled by its own copy of the Kolakoski sequence.

ETA: See next post for an alternative algorithm that avoids the recursion.

Comments:

(More comments on G+)