[seqfan] Re: Lyndon words

[M. F. Hasler]

Just in case s/o didn't find this one, since it seems not so well Xref'd:

A102659 : List of Lyndon words on {1,2} sorted first by length and
then lexicographically.
1,2,12,112,122,1112,1122,1222,...

This seems to me the most natural encoding of binary Lyndon words.

Of course, no objection on the decimal encoding you proposed
(yet, an encoding of the above as base-3 numbers seems also quite natural).

Regards,
Maximilian

On Sat, Mar 8, 2014 at 8:28 PM,  <franktaw at netscape.net> wrote:
> The empty string is also a Lyndon word, and it can be encoded with the first
> option as "1".
>
> "Lyndon words with a leading 1, converted to decimal." works for me.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Wouter Meeussen <wouter.meeussen at telenet.be>
> To: seqfan <seqfan at list.seqfan.eu>
> Sent: Sat, Mar 8, 2014 6:21 pm
> Subject: [seqfan] Lyndon words
>
>
> In http://oeis.org/A001037  under 'Example' and in
> http://en.wikipedia.org/wiki/Lyndon_word
> under 'Enumeration' we find the binary Lyndon words themselves (not their
> counts) as
> 0,1,01,001,011,0001,0011,0111,00001,00011,00101,00111,01011,01111,...
> Since each starts with a zero bit, I can see two ways of encoding these as
> decimal numbers:
> either prepend a "1" bit
> {2,3,5,9,11,17,19,23,33,35,37,39,43,47,65,67,69,71,75,77,79,87,95,...}
> or switch  1's and 0's .
> {1,0,2,6,4,14,12,8,30,28,26,24,20,16,62,60,58,56,52,50,48,40,32,...}
> The first seems more natural, and produces an increasing sequence.
> For such sequence, split in runs by bit-count, the number of Lyndon words in
> each run is A001037.
>
> Would you also prefer the first option, and, if so, how should I name it?
>
> Wouter.
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/