Visualizing the Kolakoski Sequence

Year: 2023 Authors: Ulrich Reitebuch; Henriette-Sophie Lipschütz; Konrad Polthier

Core claim

Placing Kolakoski sequence elements on a spiral creates an interpretable representation of prediction links and run structure, including generalized Kolakoski sequences.

Topics

integer sequence visualization, self-generating sequences, spiral geometry, generalized Kolakoski sequences

Domains

number theory, discrete mathematics, symbolic dynamics, fractal sequences, data visualization, algorithmic art, mathematical art, generative design

Methods

spiral mapping, graph connection encoding, parameterized functions, handmade artwork

Media

crayon on plywood, spiral line segments, color palettes, digital figure renderings

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2023 Conference Proceedings

Visualizing the Kolakoski Sequence

Ulrich Reitebuch ${}^1$ , Henriette-Sophie Lipschütz ${}^2$ , and Konrad Polthier ${}^3$

Department of Mathematics and Computer Science, Freie Universität, Berlin, Germany ${}^1$ Ulrich.Reitebuch@fu-berlin.de, ${}^2$ Henriette.Lipschuetz@fu-berlin.de, ${}^3$ Konrad.Polthier@fu-berlin.de

Abstract

The Kolakoski sequence is a self-generating sequence consisting of 1’s and 2’s only. In addition to the several visualizations of this sequence known, in this paper, a representation is presented illustrating different properties of the Kolakoski sequence and of its generalizations by placing the sequence elements on a spiral.

The Kolakoski Sequence

Visualizations of integer sequences such as the Fibonacci or the Recamán sequence using different tools like color or geometric realizations regularly catch the attention of a broad audience. For visualizations of a wide selection of integer sequences, see [5]. This paper focuses on a self-generating integer sequence on the alphabet $\{1,2\}$ , appearing as A000002 in [3]. Let n \in \mathbb{N}_{>0} , then the sequence $k(n)$ is defined as follows:

• the sequence $k(n)$ consists of 1’s and 2’s only, $k(1)=1$
• $k(n)$ is the length of the $n$ -th run.

A run is a finite part of the sequence consisting of consecutive equal elements. The terms of $k(n)$ are predicted by the length of the runs as well as the run lengths of $k(n)$ are predicted by the terms of $k(n)$ . Hence, the sequence is a fractal one. By definition, the first run is of length 1 and consists of a single 1. It is followed by the second run $k(2)$ of length 2 which gives two consecutive 2’s (otherwise there would be three consecutive 1’s). The next run of length $k(3)$ consists of 1’s and is of length $k(3)=2$ (Figure 1).

Figure 1: Construction of first six elements of the sequence. Each box shows a run, while the arrows below the boxes indicate the run predicted by the element the arrow is coming from. Reversing the arrows allows for a reconstruction of the box lengths from the sequence elements.

Therefore, the first 34 elements of this sequence are 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1. Alternatively, one could choose $k(1)=2$ . Then the sequence would look the same apart from the first missing element, i.e., the 1 listed in the definition.

In 1965, the American mathematician William George Kolakoski described this sequence, which was later named Kolakoski sequence [6]. In fact, some authors refer to the Oldenburger-Kolakoski sequence to remind the reader of Rufus Oldenburger, an American mathematician who described this sequence in 1939 [4]. It is still an unsolved problem whether the density of 1’s is equal to $\frac{1}{2}$ . The Czech mathematician and computer scientist Václav Chvátal showed that the density of 1’s is less than 0.50084 [2].

Reitebuch, Lipschütz, and Polthier

Figure 2: From left to right: distribution of elements on a spiral [7]; distribution of elements on an Archimedean spiral; 1 and 2 connected to predicting element and to predicted elements.

Placing the Sequence Elements on a Spiral

Each element appearing in $k(n)$ knows who predicted it and who it predicts. To illustrate these connections, the elements of $k(n)$ are distributed on a spiral such that each winding contains the elements predicted by those placed on the previous winding. The following parameterization serves as starting point

The function $a$ serves as the radius function while $b$ defines the angular distribution. For some constant $C\in \mathbb{R}\setminus \{0\}$, $a(t)=C\cdot b(t)$ gives an Archimedean spiral. In Figure 2 leftmost, the distribution of points is chosen such that each 2 divides the corresponding section of the following winding in two parts of equal length, indicated by $\bullet$. Runs are separated by $l$. Further, one can observe that the elements on each winding are placed irregularly on the spiral. From now on, for higher regularity, the elements $k(n)$ are placed at $(x(n),y(n){)}^T$. If the density of 1’s in the sequence is $\frac{1}{2}$, then the number of predicted elements is $\frac{3}{2}$ the number of predicting elements and grows exponentially, on average. With a distribution on an Archimedean spiral, the angles between different branches get more acute with increasing number of windings (Figure 3). A suitable choice for $a$ and $b$ to show the entire sequence on a (non-Archimedean) spiral bounded by a circular region and to distribute the elements without intersecting connections is for t > 0

Figure 3: From left to right: elements placed on a spiral with $a(t)=b(t)=b_s(t)$; angles getting more acute towards the outer windings; on a spiral with $a(t)=a_s(t)$, $b(t)=b_s(t)$, see Equation 1; elements with connecting line segments.

Visualizing the Kolakoski Sequence

Artistic Realization

As indicated in Figure 3, the spiral that the elements of the Kolakoski sequence are placed on serves as a path along which the elements can be enumerated in order of appearance. For $n\ge 2$ , fix an arbitrary element $e$ on the spiral. The turquoise line segments in Figure 2 connect the element $e$ with its predicting element and the one or two elements it predicts. Hence the Kolakoski sequence can be read off from the graphic representations shown in Figure 2 exemplary. The number of turquoise line segments incident to $e$ corresponds to the predicting element plus the number of predicted elements. Hence, for $k(n)$ as defined in the very beginning, there are either two or three such line segments, where two line segments correspond to $e$ being a 1 while three line segments correspond to $e$ being a 2.

The handmade artworks shown in Figure 4 present a tree-like realization of the Kolakoski sequence. The connection graph shown in turquois narrowing towards the bounding circle is called tree-like since the self-reference indicated in Figure 1 forms a loop placed at the center of the artwork. The self-predicting 1 in the beginning was omitted to keep the tree-like structure connected. The vertices of the connection graph are omitted to emphasize the tree-like structure and in order to still be able to retrace the connections between the single branches the spiral shown in dark blue is maintained. In total, two colors were used for the realization shown in Figure 4. The chosen turquois and dark blue contrast well, also with the ivory-colored background. The reduced color palette does not distract from the abstract and detailed structure displayed in the artwork.

In the artwork shown on the right hand side in Figure 4, the tree-like structure is colored with respect to the lengths of paths connecting two branch points. The shortest paths connect two 2’s directly, shown in light blue, while the path segment belonging to the longest path in the depicted section consists of eleven consecutive 1’s, shown in dark violet in lower right. Hence, eleven different colors were chosen in total. The color palette used here consists of shades of blue and green mainly, to replenish the colors used in the artwork created first and in order to give the result a more fluid appearance. While it is clear from the definition that there are paths consisting of 2’s only of infinite length, it is not known whether this is true for the 1’s as well.

Figure 4: Left: artwork by Ulrich Reitebuch, acrylic paint on plywood, $42.4\mathrm{cm}\times 42.4\mathrm{cm}$ , 2022, showing the Kolakoski sequence visualized as a tree-like structure under a spiral. Right: artwork by Henriette-Sophie Lipschütz, crayon on plywood, $42.5\mathrm{cm}\times 42.5\mathrm{cm}$ , 2023, showing paths in the tree-like visualization of the Kolakoski sequence colored by length.

Reitebuch, Lipschütz, and Polthier

The Kolakoski sequence can be generalized by choosing numbers different from 1 and 2 or a different amount of numbers to determine the lengths of runs and the elements of the sequence. The definition given in the beginning uses the numbers 1 and 2. This original definition is sometimes denoted by $\mathrm{Kol}(1,2)$ . Similar to this definition, one can define generalized Kolakoski sequences on three or four elements. A detailed description of specific examples is provided by the OEIS [3], for example sequences A064353, A071820, A079729, and A079730.

In Figure 5, four generalized Kolakoski sequences are shown in a representation similar to the one depicted in Figure 4. The radius function in Equation 1 was generalized to $a(t)=\frac{t}{t+c_a}$ , $c_a\in \mathbb{R}$ , to create the images shown in Figure 5. Further, the angle distribution was adapted to handle the changed number of predicted elements. Hence, the function $b$ is generalized to $b(t)=2\pi \frac{\log (t)}{\log (c_b)}$ , c_b \in \mathbb{R}_{>1} .

Figure 5: Shown are four generalized Kolakoski sequences for different run lengths. From left to right: $\text{Kol}(1,3)$ $c_a=20$ , and $c_b=2.2055694$ ; $\text{Kol}(2,3)$ , $c_a=24$ , and $c_b=2.5$ ; $\text{Kol}(1,2,3)$ , $c_a=32$ , and $c_b=2$ ; $\text{Kol}(1,2,3,4)$ , $c_a=24$ , and $c_b=2.5$ . The exact values of the $c_b$ ‘s are unknown except in the $\text{Kol}(1,3)$ case [1]. Hence the values mentioned are guesses.

Summary and Conclusion

In this paper, already existing visualizations of the Kolakoski sequence inspired a different representation which illustrates the connections between the elements of the sequence in a captivating way. The fractal-like structure achieved gives rise to further questions such as the distribution of line segments of specific lengths connecting only elements which are represented by a 1.

References

[1] M. Baake and B. Sing. “Kolakoski-(3, 1) Is a (Deformed) Model Set.” Canadian Mathematical Bulletin, vol. 47, no. 2, 2004, pp. 168–190. [2] V. Chvátal. “Notes on the Kolakoski Sequence.” Technical Report 93-84. DIMACS, 1993. [3] OEIS Foundation Inc. (2023), The On-Line Encyclopedia of Integer Sequences, Published electronically at http://oeis.org. [4] R. Oldenburger. “Exponent trajectories in symbolic dynamics.” Trans. Amer. Math. Soc., vol. 46, pp. 453-466, 1939. https://doi.org/10.2307%2F1989933. [5] K. E. Stange, “Numberscope,” 2023. https://math.katestange.net/numberscope/. [6] A. M. Vaidya et al. “Advanced Problems: 5300-5309.” The American Mathematical Monthly, vol. 72, no. 6, pp. 673-675, 1965. https://doi.org/10.2307/2313883. [7] Background and coloring of image edited by the authors. https://upload.wikimedia.org/wikipedia/commons/1/1d/Kolakoski_sequence_spiral.svg.