

A329358


Numbers whose binary expansion has Lyndon and coLyndon factorizations of equal lengths.


2



1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 74, 83, 85, 86, 89, 93, 99, 107, 119, 127, 129, 138, 150, 153, 163, 165, 174, 177, 185, 189, 195, 203, 205, 219, 231, 255, 257, 266, 273, 274, 278, 291, 294, 297, 302, 305, 310, 313, 323, 325, 333, 341
(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).
Similarly, the coLyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a coLyndon word is a finite sequence that is prime with respect to the coLyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted coLyndon factorization (1)(100).


LINKS

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


FORMULA

A211100(a(n)) = A329312(a(n)).


EXAMPLE

The binary expansions of the initial terms together with their Lyndon and coLyndon factorizations:
1: (1) = (1) = (1)
3: (11) = (1)(1) = (1)(1)
5: (101) = (1)(01) = (10)(1)
7: (111) = (1)(1)(1) = (1)(1)(1)
9: (1001) = (1)(001) = (100)(1)
15: (1111) = (1)(1)(1)(1) = (1)(1)(1)(1)
17: (10001) = (1)(0001) = (1000)(1)
21: (10101) = (1)(01)(01) = (10)(10)(1)
27: (11011) = (1)(1)(011) = (110)(1)(1)
31: (11111) = (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)
33: (100001) = (1)(00001) = (10000)(1)
45: (101101) = (1)(011)(01) = (10)(110)(1)
51: (110011) = (1)(1)(0011) = (1100)(1)(1)
63: (111111) = (1)(1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)(1)
65: (1000001) = (1)(000001) = (100000)(1)
73: (1001001) = (1)(001)(001) = (100)(100)(1)
74: (1001010) = (1)(00101)(0) = (100)(10)(10)
83: (1010011) = (1)(01)(0011) = (10100)(1)(1)


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, #]]&]]]];
colynQ[q_]:=Array[Union[{RotateRight[q, #], q}]=={RotateRight[q, #], q}&, Length[q]1, 1, And];
colynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[colynfac[Drop[q, i]], Take[q, i]]]@Last[Select[Range[Length[q]], colynQ[Take[q, #]]&]]];
Select[Range[100], Length[lynfac[IntegerDigits[#, 2]]]==Length[colynfac[IntegerDigits[#, 2]]]&]


CROSSREFS

The version counting compositions is A329394.
The version ignoring the most significant digit is A329395.
Binary Lyndon/coLyndon words are counted by A001037.
Lyndon/coLyndon compositions are counted by A059966.
Lyndon compositions whose reverse is not coLyndon are A329324.
Binary Lyndon/coLyndon words are constructed by A102659 and A329318.
Cf. A060223, A211100, A275692, A328596, A329312, A329313, A329326, A329398.
Sequence in context: A258159 A238257 A305409 * A180204 A006995 A163410
Adjacent sequences: A329355 A329356 A329357 * A329359 A329360 A329361


KEYWORD

nonn


AUTHOR

Gus Wiseman, Nov 15 2019


STATUS

approved



