cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A211100 Number of factors in Lyndon factorization of binary expansion of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 4, 3, 4, 4, 5, 2, 3, 2, 4, 3, 3, 2, 5, 3, 4, 3, 5, 4, 5, 5, 6, 2, 3, 2, 4, 2, 3, 2, 5, 3, 4, 2, 4, 3, 3, 2, 6, 3, 4, 3, 5, 4, 4, 3, 6, 4, 5, 4, 6, 5, 6, 6, 7, 2, 3, 2, 4, 2, 3, 2, 5, 3, 3, 2, 4, 2, 3, 2, 6, 3, 4, 3, 5, 4, 3, 2, 5, 3, 4, 3, 4, 3, 3, 2, 7, 3, 4, 3, 5, 3, 4, 3, 6, 4, 5, 3, 5, 4, 4, 3, 7, 4, 5, 4, 6, 5, 5, 4, 7
Offset: 0

Views

Author

N. J. A. Sloane, Mar 31 2012

Keywords

Comments

Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). a(n) = number of factors in Lyndon factorization of binary expansion of n.
It appears that a(n) = k for the first time when n = 2^(k-1)+1.
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. - Gus Wiseman, Nov 12 2019

Examples

			n=25 has binary expansion 11001, which has Lyndon factorization (1)(1)(001) with three factors, so a(25) = 3.
Here are the Lyndon factorizations for small values of n:
.0.
.1.
.1.0.
.1.1.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.1.0.0.0.
.1.001.
.1.01.0.
.1.011.
.1.1.0.0.
...

References

  • M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
  • G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

Links

Crossrefs

Cf. A001037 (number of Lyndon words of length m); A102659 (list thereof).
A211095 and A211096 give information about the smallest (or rightmost) factor. Cf. A211097, A211098, A211099.
Row-lengths of A329314.
The "co-" version is A329312.
Positions of 2's are A329327.
The reversed version is A329313.
The inverted version is A329312.
Ignoring the first digit gives A211097.
Cf. A059966, A060223, A275692, A296658, A328594, A328595, A328596, A329131, A329325, A329326.

Programs

  • 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,#]]&]]]];
Table[Length[lynfac[IntegerDigits[n,2]]],{n,0,30}] (* Gus Wiseman, Nov 12 2019 *)

A211097 Number of factors in Lyndon factorization of binary vectors of lengths 1, 2, 3, ...

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 3, 3, 4, 1, 2, 1, 3, 2, 2, 1, 4, 2, 3, 2, 4, 3, 4, 4, 5, 1, 2, 1, 3, 1, 2, 1, 4, 2, 3, 1, 3, 2, 2, 1, 5, 2, 3, 2, 4, 3, 3, 2, 5, 3, 4, 3, 5, 4, 5, 5, 6, 1, 2, 1, 3, 1, 2, 1, 4, 2, 2, 1, 3, 1, 2, 1, 5, 2, 3, 2, 4, 3, 2, 1, 4, 2, 3, 2, 3, 2, 2, 1, 6, 2, 3, 2, 4, 2, 3, 2, 5, 3, 4, 2, 4, 3, 3, 2, 6, 3, 4, 3, 5, 4, 4, 3, 6, 4, 5
Offset: 1

Views

Author

N. J. A. Sloane, Apr 01 2012

Keywords

Comments

Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). Here we look at the Lyndon factorizations of the binary vectors 0,1, 00,01,10,11, 000,001,010,011,100,101,110,111, 0000,...
For the largest (or leftmost) factor see A211098, A211099.
The smallest (or rightmost) factors are given by A211095 and A211096, offset by 2.

Examples

			Here are the Lyndon factorizations of the first few binary vectors:
.0.
.1.
.0.0.
.01.
.1.0.
.1.1.
.0.0.0.
.001.
.01.0. <- this means that the factorization is (01)(0), for example
.011.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.0.0.0.0.
...

References

  • M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
  • G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

Links

Crossrefs

A211098 and A211099 give information about the largest (or leftmost) factor.
Cf. A211095, A211096.
Row-lengths of A329325.
The "co" version is A329400.
Retaining the first digit gives A211100.
Binary Lyndon words are counted by A001037 and constructed by A102659.
Numbers whose reversed binary expansion is Lyndon are A328596.
Cf. A059966, A060223, A275692, A329312, A329313, A329314, A329326.

Programs

  • 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,#]]&]]]];
Table[Length[lynfac[Rest[IntegerDigits[n,2]]]],{n,2,50}] (* Gus Wiseman, Nov 14 2019 *)

A211096 Smallest (i.e., rightmost) Lyndon word in the Lyndon factorization of the binary representation of n (written using 1's and 2's rather than 0's and 1's, since numbers > 0 in the OEIS cannot begin with 0).

Original entry on oeis.org

1, 2, 1, 2, 1, 12, 1, 2, 1, 112, 1, 122, 1, 12, 1, 2, 1, 1112, 1, 1122, 1, 12, 1, 1222, 1, 112, 1, 122, 1, 12, 1, 2, 1, 11112, 1, 11122, 1, 11212, 1, 11222, 1, 112, 1, 12122, 1, 12, 1, 12222, 1, 1112, 1, 1122, 1, 12, 1, 1222, 1, 112, 1, 122, 1, 12, 1, 2, 1, 111112, 1, 111122, 1, 111212, 1, 111222, 1, 112, 1, 112122, 1, 112212, 1, 112222, 1, 1112, 1, 1122, 1
Offset: 0

Views

Author

N. J. A. Sloane, Mar 31 2012

Keywords

Comments

See A211095 and A211097 for further information, including Maple programs.

Examples

			n=25 has binary expansion 11001, which has Lyndon factorization (1)(1)(001) with three factors. The rightmost factor is 001, which we write as a(25) = 112.
The real sequence (written with 0's and 1's rather than 1's and 2's) is:
0, 1, 0, 1, 0, 01, 0, 1, 0, 001, 0, 011, 0, 01, 0, 1, 0, 0001, 0, 0011, 0, 01, 0, 0111, 0, 001, 0, 011, 0, 01, 0, 1, 0, 00001, 0, 00011, 0, 00101, 0, 00111, 0, 001, 0, 01011, 0, 01, 0, 01111, 0, 0001, 0, 0011, 0, 01, 0, 0111, 0, 001, 0, 011, ...

Crossrefs

Cf. A211100, A211095, A211097, A211098, A211099.

Formula

a(2k) is always 1 (i.e., 0).
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.