Fun With Sequences

I like sequences that have non-conventional definitions. For example, there is the very non-equational Look and Say Sequence made famous by Conway:

$\{1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131211, \ldots \}$

This starts with the seed value 1, and each successive term is generated by looking at the previous term, saying the numbers appearing there out loud, and writing down the numbers you find yourself saying. For instance, the term ‘111221’ becomes “Three ones, two twos, one one”, which transliterates to ‘312211’.

Despite this crazy generating rule, there is actually a lot of structure to be found in this sequence. Conway found that certain strings of digits, once created, never interacted with those to their left or right again, instead going through an internal ‘life cycle’, growing and changing until it reached a point where it was a string of several such atomic strings joined together; each of these then went off in their own life cycle like some strange numerical mitosis. Conway actually named these atomic strings after the elements, since he found 92 such atomic strings containing the numbers 1, 2, and 3 alone, and two ‘transuranic’ strings for each other natural number.

Conway also found that the ratio of the length of successive terms approaches a constant, and gave a degree-71 polynomial of which this constant is the only real root.

The Look and Say Sequence is surprisingly fruitful, given how non-mathematical its rule seems.

Advertisements

Complete Word Tours

Suppose we were to take a finite alphabet $\mathbb{A}_n$ of $n$ letters, say $\{ 0, 1, \ldots, n-1\}$, and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:

$\{00, 01, \ldots, 0(n-1), 10, 11, \ldots, (n-1)(n-1)\}$

and there are $n^2$ many of these. Let’s denote the set of length-$m$ words using the alphabet $\mathbb{A}_n$ by $\mathbb{W}^m_n$.

What I am interested in now is “For a given $n$ and $m$, what is the minimum length string of letters I can write down and still be sure that every word in $\mathbb{W}^m_n$ appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.

Example:

01100

contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of $\mathbb{W}^2_2$ appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,

0011101000

and

0201221100

are examples of optimal tours through $\mathbb{W}^3_2$ and $\mathbb{W}^2_3$ respectively, as they both have this property that each letter added after the first $m$ adds a previously unseen word.

Notice I’ve introduced the terminology tour for any string $\tau$ that contains all words in a given $\mathbb{W}^m_n$, with optimal tour being the tour $\tau^m_n$ that is of minimum possible length for that $m$ and $n$.