[seqfan] Lyndon factorizations [was Re: OEIS historic sequences]

[Antti Karttunen]

> Message: 13
> Date: Mon, 1 Jun 2015 13:05:13 -0400
> From: Frank Adams-Watters <franktaw at netscape.net>
> To: seqfan at list.seqfan.eu, njasloane at gmail.com
> Subject: [seqfan] Lyndon factorizations [was Re: OEIS historic
>         sequences]
> Message-ID: <14db0159495-ddb-d327 at webprd-m77.mail.aol.com>
> Content-Type: text/plain; charset=utf-8
>
> Just looking at A211096 and A211099, two other ways to represent these sequences immediately occur to me.
>
> One is to stick a "1" at the beginning of the binary representation of each member:
>
> 10, 11, 10, 11, 10, 101, ...
>
> The second is to interpret each term, written as I just did [above], as a binary number, and convert to decimal:
>
> 2, 3, 2, 3, 2, 5, ...

I use this latter method. Tentatively, I call them "msb-capped binary
codes" (better suggestions?), and there are several sequences cooking
in my draft queue that encode boundaries of holeless polyhexes (or a
slightly more inclusive family:
fusenes/benzenoids/whatever-they-are-called, I'm not yet sure about
the exact scope of each term in this field, but I will find out).

If we use this unambiguous encoding, then we already have some good
tools at our disposal:

https://oeis.org/A059893 for reversing.
https://oeis.org/A080541 and A080542 for rotating.
https://oeis.org/A256999 for finding the largest representative from
each necklace class.
https://oeis.org/A257250 for listing those largest representatives.
(would need also analogous sequences for the smallest representatives)

For each n and also for each term of A257250 it would be nice to
create a sequence b(n) which lists the size of the cycle of that n in
A080541, and also A000523(n)/b(n) [the size of the necklace per the
size of the cycle], and then those cases for which the latter is 1,
that is, ones which are aperiodic, i.e., corresponding to Lyndon words
(modulo some details?). And if I recall right what was said in some of
the papers of Frank Ruskey (on his website) that I read years ago, one
can convert these latter ones with some magic trick to polynomials
that are irreducible over GF(2)[X] (A014580).



>
> Franklin T. Adams-Watters
>

Best regards,

Antti Karttunen

PS. As what comes to David Corneth's suggestion that it would be nice
to see which sequences are most cross-referenced (after A000040, that
is, ;-), I agree, but that functionality would be best implemented by
developing the OEIS server software itself. And in general, keep the
platonic permanent world of mathematics separate from our contingent
temporal world.

PS2. When replying, please add my address to the CC:-line, because I
only receive digests from SeqFan-list, and they might take some time
to arrive.