8
$\begingroup$

For information on the sequence mentioned in the title, see http://en.wikipedia.org/wiki/Look-and-say_sequence. This is an original problem.

Suppose instead of "describing" the numbers in a string in order, one counts the digits globally and, for convention, lists then in numerical order. That is, whereas in Conway's sequence $21\rightarrow 1211$, in my version, $21\rightarrow 1112$. Starting with the initial string 1, an interesting thing happens at the 13th iteration: we come upon the string $21322314$ which "describes" itself. We may think of this as a fixed point in the iteration process.

At this point, a distinction needs to be made. I'd like to be able to answer questions about general strings, including those with numbers of more than one digit. That is, I'd like to be able to discuss strings which naturally lead to, say, ten 1's or thirteen 4's. Once a multi-digit number is in a string, we have a choice. We may either respect the integrity of the number or split it into its constituent digits. For example, we may either say "13 is one 1 and one 3" or "13 is one $\underline{13}$." Call these varations A and B.

Here are some questions I've thought about regarding this sequence:

  1. Does every string in variations A and B terminate? That is, does the process lead to a fixed point. I have answered this question for A in the affirmative, but not for B. I strongly suspect it holds for B as well.

  2. Notice that sometimes strings can terminate in a nontrivial cycle: notationally, $S_1→S_2→...→S_n→S_1.$ Call this a cycle of length $n$. (The biggest cycle I've found from experimentation is of length 6). Assuming strings terminate in both A and B and given an arbitrary string $S$, can one put an upper bound on on the cycle length of its eventual fixed point?

  3. Further, given an arbitrary string $S$ in A or B, what can one say about the amount of iterations it takes for $S$ to terminate? What about its eventually string length?

  4. Suppose we abandon talk of "strings" and instead think of the objects as multisets. This is natural given how much multiplicity matters in this discussion. Let $M_\mathbb{N}$ denote the set of multisets with elements in $\mathbb{N}$. Then the process of "looking and saying" is a function $J:M_\mathbb{N}\rightarrow M_\mathbb{N}$. Is there a natural way to impose meaningful structure on $M_\mathbb{N}$ so that the above questions involving $J$ are easier to answer? (For example, if there were a way to define addition, so that if $S\in C_1$ and $T\in C_2$ and $S+T\in C_3$ for equivalence classes $C_i$, then a homomorphism respecting this would be nice.)

  5. (Personally, my favorite question.) Say two strings $S$ and $T$ are similar if they terminate in the same cycle. This is clearly an equivalence relation and it thus partitions $M_\mathbb{N}$. In variation B, it seems clear that there are infinitely many equivalence classes. In variation A, however, the fixed points are artifacts of the base $b$ in which we construe the strings. In this variation, how many equivalence classes are there as a function of $b$? Just a heads up: I've had several practicing mathematicians who work in various fields tell me that this question is unfeasibly difficult.

Thanks.

  • 0
    That would be very helpful, Austin. Thank you.2012-10-26

1 Answers 1