login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A329317 Length of the Lyndon factorization of the reversed first n terms of A000002. 11
1, 2, 3, 2, 2, 3, 3, 4, 5, 4, 5, 6, 5, 3, 4, 4, 2, 3, 4, 3, 4, 3, 3, 4, 4, 5, 6, 5, 4, 5, 5, 2, 3, 3, 4, 5, 4, 5, 6, 5, 3, 4, 4, 5, 6, 5, 6, 5, 3, 4, 4, 2, 3, 4, 3, 4, 5, 4, 3, 4, 4, 5, 6, 5, 6, 7, 6, 4, 5, 5, 3, 4, 4, 5, 6, 5, 6, 5, 4, 5, 6, 5, 6, 7, 6, 5, 6 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).

LINKS

Table of n, a(n) for n=1..87.

EXAMPLE

The sequence of Lyndon factorizations of the reversed initial terms of A000002 begins:

   1: (1)

   2: (2)(1)

   3: (2)(2)(1)

   4: (122)(1)

   5: (1122)(1)

   6: (2)(1122)(1)

   7: (12)(1122)(1)

   8: (2)(12)(1122)(1)

   9: (2)(2)(12)(1122)(1)

  10: (122)(12)(1122)(1)

  11: (2)(122)(12)(1122)(1)

  12: (2)(2)(122)(12)(1122)(1)

  13: (122)(122)(12)(1122)(1)

  14: (112212212)(1122)(1)

  15: (2)(112212212)(1122)(1)

  16: (12)(112212212)(1122)(1)

  17: (1121122122121122)(1)

  18: (2)(1121122122121122)(1)

  19: (2)(2)(1121122122121122)(1)

  20: (122)(1121122122121122)(1)

For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so a(13) = 5.

MATHEMATICA

lynQ[q_]:=Array[Union[{q, RotateRight[q, #]}]=={q, RotateRight[q, #]}&, Length[q]-1, 1, And];

lynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[lynfac[Drop[q, i]], Take[q, i]]][Last[Select[Range[Length[q]], lynQ[Take[q, #]]&]]]];

kolagrow[q_]:=If[Length[q]<2, Take[{1, 2}, Length[q]+1], Append[q, Switch[{q[[Length[Split[q]]]], q[[-2]], Last[q]}, {1, 1, 1}, 0, {1, 1, 2}, 1, {1, 2, 1}, 2, {1, 2, 2}, 0, {2, 1, 1}, 2, {2, 1, 2}, 2, {2, 2, 1}, 1, {2, 2, 2}, 1]]]

kol[n_Integer]:=Nest[kolagrow, {1}, n-1];

Table[Length[lynfac[Reverse[kol[n]]]], {n, 100}]

CROSSREFS

Row-lengths of A329316.

The non-reversed version is A329315.

Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.

Sequence in context: A242789 A076733 A079643 * A118480 A104377 A109337

Adjacent sequences:  A329314 A329315 A329316 * A329318 A329319 A329320

KEYWORD

nonn

AUTHOR

Gus Wiseman, Nov 11 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 01:31 EDT 2021. Contains 343198 sequences. (Running on oeis4.)