[seqfan] Re: help needed with former sequence A138036

[Charles Greathouse]

>  [T]his computation shows that [...] squares are unavoidable over
>  3 letters, since every word of length 8 turns out to contain them.

I thought that there were infinite squarefree words over a
three-letter alphabet, like A099054 (a result of Thue, I think, but
not mentioned there or at A005679/A036584/A100337).  Zeilberger has a
paper in the JIS that shows that they can be arbitrarily long.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Sun, Sep 4, 2011 at 5:21 PM,  <hv at crypt.org> wrote:
> "N. J. A. Sloane" <njas at research.att.com> wrote:
> :Dear Seqfans, I admit I don't speak Mathematica.
> :Here is the definition of the former sequence A138036
> :(now deleted from the OEIS, but you can read the History):
> :
> :Clear[a]; a = With[{n = 8, k = 3}, NestList[DeleteCases[Flatten[Map[Table[Append[ #, i - 1], {i, k}] &, # ], 1], {___, u__, v__} /; Sort[{u}] == Sort[{v}]] &, {{}}, n]]; Flatten[a]
> :
> :which apparently produces
> :
> :{{}},
> :{{0}, {1}, {2}},
> :{{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}},
> :{{0, 1, 0}, {0, 1, 2}, {0, 2, 0}, {0, 2, 1}, {1, 0, 1}, {1, 0, 2}, {1, 2, 0}, {1, 2, 1}, {2, 0, 1}, {2, 0, 2}, {2, 1, 0}, {2, 1, 2}},
> :{{0, 1,0, 2}, {0, 1, 2, 0}, {0, 1, 2, 1}, {0, 2, 0, 1}, {0, 2, 1, 0}, {0, 2, 1, 2}, {1, 0, 1, 2}, {1, 0, 2, 0}, {1, 0, 2, 1}, {1, 2, 0, 1}, {1, 2, 0, 2}, {1, 2, 1, 0}, {2, 0, 1, 0}, {2, 0, 1, 2}, {2, 0, 2, 1}, {2, 1, 0, 1}, {2, 1, 0, 2}, {2, 1, 2, 0}},
> :{{0, 1, 0, 2, 0}, {0, 1, 0, 2, 1}, {0, 1, 2, 0, 1}, {0, 1, 2, 0, 2}, {0, 1, 2, 1, 0}, {0, 2, 0,1, 0}, {0, 2, 0, 1, 2}, {0, 2, 1, 0, 1}, {0, 2, 1, 0,2}, {0, 2, 1, 2, 0}, {1, 0,1, 2, 0}, {1, 0, 1, 2, 1}, {1, 0, 2, 0, 1}, {1, 0, 2, 1, 0}, {1, 0, 2, 1, 2}, {1, 2, 0, 1, 0}, {1, 2, 0, 1, 2}, {1, 2, 0, 2, 1}, {1, 2, 1, 0, 1}, {1, 2, 1, 0, 2}, {2, 0,1, 0, 2}, {2, 0, 1, 2, 0}, {2, 0, 1, 2, 1}, {2, 0, 2,1, 0}, {2, 0, 2, 1, 2}, {2,1, 0, 1, 2}, {2, 1, 0, 2, 0}, {2, 1, 0, 2, 1}, {2, 1, 2, 0, 1}, {2, 1, 2, 0, 2}},
> :...
> :
> :which then became the sequence
> :
> :0, 1, 2, 0, 1, 0, 2, 1, 0, 1, 2, 2, 0, 2, 1, 0, 1, 0, 0, 1, 2, 0, 2, 0, 0, 2, 1, 1, 0, 1, 1, 0, 2, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 0, 2, 1, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 1, 2, 0, 2, 1, 2, 1, 0, 2, 0, 1, 0, 2, 0, ...
> :
> :which was A138036
> :
> :which was recently deleted by the editors.
> :
> :But the sequence looks interesting. Can anyone supply a definition
> :in English for it? Or is it indeed not worthy of being included?
>
> I don't speak Mathematica; by eye, the first list looks like all
> square-free sequences in a 3-symbol alphabet ordered first by length,
> then lexically.
>
> Looking back at the history, it seems to be a demonstration of this:
>
>  [T]his computation shows that [...] squares are unavoidable over
>  3 letters, since every word of length 8 turns out to contain them.
>
> .. unfortunately swaddled in so much semi-mystical verbiage as to be
> effectively encrypted.
>
> Replacing the mysticism with a clear explanation would probably be
> sufficient to make this worth keeping.
>
> Hugo
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>