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!)
A211100 Number of factors in Lyndon factorization of binary expansion of n. 46
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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

REFERENCES

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.

G. Melancon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

N. J. A. Sloane, Maple programs for A211100 etc.

EXAMPLE

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.

...

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 *)

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.

Sequence in context: A217865 A185166 A276555 * A329326 A105264 A063787

Adjacent sequences:  A211097 A211098 A211099 * A211101 A211102 A211103

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Mar 31 2012

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 September 26 01:25 EDT 2020. Contains 337346 sequences. (Running on oeis4.)