16
$\begingroup$

I have a straightforward question about Conway's "Look and Say Sequence (A005150):

The integer sequence beginning with a single digit in which the next term is obtained by describing the previous term. Starting with 1, the sequence would be defined by "1, one 1, two 1s, one 2 one 1," etc., and the result is 1, 11, 21, 1211, 111221, ....

Source: http://mathworld.wolfram.com/LookandSaySequence.html

Question: Is this sequence strictly increasing?

It is known that, asymptotically, the number of digits in each term grows by a little more than 30%:

if $L_n$ is the number of digits in the $n$-th term in the sequence, then

$\lambda := \displaystyle{\lim_{n\to\infty}\frac{L_{n+1}}{L_n} = 1.303577269\dots}$

where $\lambda$ is the unique positive real root of the following degree-71 polynomial: [...]

Source: http://www.nathanieljohnston.com/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/

However, is this growth monotonic everywhere in the sequence, or do there exist a finite number of pathological examples where the $(n+1)$-th term is smaller than the $n$-th term?

Surely, this depends on the initial seed of the sequence. For example, under the "look and say" operation, $111222\to 3132$ decreases. Is it known whether there are any instances of behavior like this in the sequence where the seed is 1?

$\endgroup$
  • 2
    $\begingroup$ @vadim123 The question here asks specifically about the sequence with the initial seed of $1$. (Incidentally, the number $22$ is mentioned in the Wolfram link in the OP...) $\endgroup$ – Benjamin Dickman Jan 5 '18 at 23:22
7
$\begingroup$

We can show that the Look and Say sequence is strictly increasing by applying the Cosmological Theorem to the sequence.

The Cosmological Theorem is an analysis of Look and Say sequences that shows there exist $92$ strings (know as elements) whose successor strings only contain these elements. It is conjectured that any string containing only $1$, $2$ and $3$, that does not contain four of the same number in succession, will decay into a string containing only these elements.

Conway applied the names of the chemical elements to these. A list of the $92$ elements with their decay patterns can be found here.

Proof

First we note that the sequence with seed $1$ is strictly increasing up to the eighth entry $1113213211$ which consists of the elements $72$ $Hf=11132$ and $50$ $Sn=13211$.

Then, by inspection, we find that only one of the $92$ elements decays into a lower number, which is $63$ $Eu=1113222$ which becomes $311332$.

Further analysis of $Eu$ shows that it has $4$ predecessor elements:

$Ga\rightarrow Eu$ $Ca$ $Ac$ $H$ $Ca$ $Zn$
$Ru\rightarrow Eu$ $Ca$ $Tc$
$Te\rightarrow Eu$ $Ca$ $Sb$
$Gd\rightarrow Eu$ $Ca$ $Co$

So, whenever the element $Eu$ is generated it is always followed by $Ca$.

$Eu$ $Ca=1113222\ 12$ which decays to $Sm$ $K=311332\ 1112$, so these combined elements increase.

The element $1$ $H=22$ is constant in that it decays to $22$, but since it cannot appear by itself it must be accompanied by increasing elements.

Thus we have shown that every string representing an element in the Cosmological Theorem, with special cases for $Eu$ and $H$, decays to a higher value string.

Hence the Look and Say sequence with seed $1$ is strictly increasing for all entries. $\square$

$\endgroup$
  • $\begingroup$ The Cosmological Theorem is an analysis of Look and Say sequences that shows there exist 92 strings (know as elements) whose successor strings only contain these elements Maybe for the uninitiated, you could add more detail to this. There's some confusion about what this means, how the elements are placed together (since just because $a$ decays to $a'$ and $b$ decays to $b'$, doesn't mean $ab$ decays to $a'b'$.) $\endgroup$ – 6005 Sep 4 '18 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.