1, 1 1, 2 1, 1 2 1 1, ...

Additional material

[ Editor: a May 1996 thread, "Strange series", in sci.math and
rec.puzzles. ]

In article <3191EE66.21DE@eso.org>, Nicolas Devillard <nDevil@eso.org>
wrote:

>1 11 21 1211 111221

>It is easy to prove that it will only be composed of digits 1, 2, 3.
>1. Do you have a simple demonstration of that fact?
>2. Are there stable points, ie numbers such as desc(x) = x ?
>3. Does the above series converge to a stable point?

Here's part of an article I wrote 7 years ago, to the day in fact,
on this topic, and it answers all of your questions; perhaps it should
be added to the rec.puzzles FAQ on this problem:

[ Editor: Chris Long's 1989 article ("More on the Compression Sequence",
11 May 1989) follows. ]

In article <3419@rpi.edu>, Mark-Jason Dominus writes:

> 2 2 is clearly a fixed string; it is the only one.

David Moews posted a proof of this similar to the following a
while back on rec.puzzles.

Consider a compressed string of length 2n.  If this string is
X = { x_1 x_2 x_3 ... x_2n }, we know that no two adjacent elements
with even subscripts have the same value.  Compress this string to
string Y.  Since no two adjacent elements with even subscripts had
the same value in the original string, the derived string Y must
have length at least 2n.  I will now show that if we compress this
string three times (i.e. compress the original string four times),
it will have length > 2n unless the original string was { 2 2 }.
 
Assume X does not strictly increase in length after four compress-
ions.  Since we've seen that the length of a string increases
monotonically after the initial compression, we see that we can
assume Y = { y_ 1 ... y_2n }.  It is not hard to see that we must
have Y = { a a b b ... } or { a a a b ... }, as otherwise the
string derived from Y would have length > 2n.  In the first case,
the derived string Z will be of the form { 2 a ... } ==> a=2; in
the second case we have Z = { 3 a ... } ==> a=3.  The second case
implies that Y = { 3 3 3 b ... } ==> X = { 3 3 3 b b b ... }, im-
possible, as X is a derived string.

We are now only left with the first case, i.e. that Y = { 2 2 b b
* ... } or { 2 2 b b b * ... }.  The first subcase implies Z =
{ 2 2 2 b ... }, which compresses to { 3 2 ... }, which gets strictly
longer upon compression.  The second subcase implies Z = { 2 2 3 b
... } ==> b=3; impossible.

Hence, if X does not strictly increase in length after four com-
pressions, we see that |X| < 4.  Since X is a derived string, this
implies that |X| = 2, i.e. n=1.  The only string of length 2 that
does not get bigger upon compression is easily seen to be { 2 2 }.

Q.E.D.

> No number larger than 3 ever appears if you start with '1', but this
> is easy to show.

Let n>3.  The appearence of a [ n x's ] ==> that the previous string
that this one was derived from had a substring of the form { x x x x },
and such a substring can never appear under the given transformation;
since this substring is not in the initial string we deduce that it
never appears.  Since the first appearence of an n must be in a sub-
string of the form [ n x's ] and not [ x n's ], we conclude that no
number >3 ever appears.

-- Chris Long <clong@cnj.digex.net>

Nicolas Devillard <nDevil@eso.org> presents this sequence of numeral
strings:
           1, 11, 21, 1211, 111221, 312211, ...

in which each string x is followed by its "descriptor" string desc(x).
The method of description is most easily given by example. Consider
111221 it can be described as "three 1's, two 2's, one 1" so
desc(111221) = 312211.

Nicolas asks:

   1) Prove every string in the sequence is composed solely of
      1's, 2's, and 3's

   2) Are there fixed-point strings -- x's such that desc(x) = x.
      (x may be any string. It need not come from our sequence.)

   3) Does our sequence eventually arrive at a fixed point?

First of all, I describe our objects as numeral strings for convenience.
In the general case we might need "numerals" greater than 9 but in this
discussion that won't happen so we will keep the terminology.

Every desc(x) is of the form a1 b1 a2 b2 a3 b3 ... Each a b pair
describes a "block" from x. e.g. x = 132221; its blocks are
1, 3, 222, 1; desc(x) = 11 13 32 11.

We will refer to the a's as "counts" and to the b's as "values". It is
obvious that successive values must be different from each other
(e.g. You cannot begin a desc(x) with 3121). Let's call this fact the
MAIN LAW.

Let's call our sequence S(i). i.e.  S(1) = 1, S(2) = 11, etc.

    1) Let B = S(k) be the first term in the sequence to have a numeral,
       say t, other than 1,2,3.  k isn't 1 so there is an  A = S(k - 1)
       such that B = desc(A). By inspection, k is not 2 so A = desc(x)
       for some x. Since A precedes B in the sequence, it contains no t.
       Then any instance of t in B is a count. Then t can't be 0 so t > 3.
       Then A contains a block of at least four consecutive equal digits.
       Such a block must contain two successive values. Contra the Main Law.

    Saving 2) for last.

    3) Our sequence contains no fixed point. More generally, no string
       in our sequence is repeated. Let m be the smallest index such that
       S(m) = S(n) for some n > m. Obviously m is not 1. Also S(i) is
       clearly one-one. Then S(m - 1) = S(n - 1) contra m is smallest
       such index.


    2) desc(22) = 22. This is the only fixed point.

       Let A = desc(A) = tu...

       Since u is the first value in desc(A), A begins with u so t = u.
       So desc(A) = tt...  Then since t is a count, t is not 0. Also
       since A = desc(desc(A)), t not > 3. (By the same argument as in
       part 1 above.)

       So A = 11...   or  A = 22...  or  A = 33...

       Case 1) A = 11. Then A describes itself as beginning with exactly
               one 1, contra.

       Case 2) A = 33...  Then A = 333... Since A = desc(A) it contains an
               even number of numerals and must have a fourth numeral, say
               A = 333x. Then A describes itself as beginning 333xxx...
               But the first and third x's violate the Main Law, contra.

       Therefore  A = 22...

       Suppose that A has a third numeral -- A = 22a... Then since
       A = desc(A),  there is a fourth numeral -- A = 22ab. Then
       (by the same argument we used to get the first two numerals of A)
       we have A = 2222..., contra the Main Law.

-- Barry Paul <bpaul@hoflink.com>