A001037 -id:A001037 - cp's OEIS frontend

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

1, 1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023, 1432613, 5170575, 18783360, 68635477, 252085716, 930138521, 3446158600, 12815663595, 47820414961, 178987624513, 671825020128, 2528212128750, 9536894664375, 36054433807398, 136583760011496

Offset: 0

David Broadhurst

Also number of asymmetric rooted plane trees with n+1 nodes. - Christian G. Bower
Conjecturally, number of irreducible alternating Euler sums of depth n and weight 3n.
a(n+1) is inverse Euler transform of A000108. Inverse Witt transform of A006177.
Dimension of the degree n part of the primitive Lie algebra of the Hopf algebra CQSym (Catalan Quasi-Symmetric functions). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 22 2006
For n>0, 2*a(n) is divisible by n (cf. A268619), 12*a(n) is divisible by n^2 (cf. A268592). - Max Alekseyev, Feb 09 2016

			a(3)=3 counts 6-periodic 000111, 001011 and 001101. a(4)=8 counts 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, and 00110101. - _R. J. Mathar_, Oct 20 2021

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. J. H. Al-Kaabi, Monomial Bases for Free Post-Lie Algebras, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See pp. 3, 6.
David J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
Gilbert Labelle and Pierre Leroux, Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Disc. Math. 157 (1996) 227-240, Eq. (1.20).
Hans Munthe-Kaas and Alexander Lundervold, On post-Lie algebras, Lie-Butcher series and moving frames, arXiv preprint arXiv:1203.4738 [math.NA], 2012. - From _N. J. A. Sloane_, Sep 20 2012
Jean-Christophe Novelli and Jean-Yves Thibon, Hopf algebras and dendriform structures arising from parking functions, arXiv:math/0511200 [math.CO], 2005.
Tilman Piesk, List of 2n-bead balanced binary Lyndon words for n=1...8
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Index entries for sequences related to rooted trees
Index entries for sequences related to Lyndon words

Cf. A003239, A005354, A000740, A007727, A086655, A289978 (multiset trans.), A001037 (binary Lyndon wds.), A074655 (3 letters), A074656 (4 letters).

A diagonal of the square array described in A051168.

with(numtheory):
a:= n-> `if`(n=0, 1,
        add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 21 2011

a[n_] := Sum[MoebiusMu[n/d]*Binomial[2d, d], {d, Divisors[n]}]/(2n); a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 02 2015 *)

a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)

from sympy import mobius, binomial, divisors
def a(n):
    return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 05 2017

def a(n):
    return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
# F. Chapoton, Apr 23 2020

a(n) = A060165(n)/2 = A007727(n)/(2*n) = A045630(n)/n.
Product_n (1-x^n)^a(n) = 2/(1+sqrt(1-4*x));  a(n) = 1/(2*n) * Sum_{d|n} mu(n/d)*C(2*d,d). Also Moebius transform of A003239. - Christian G. Bower
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 11 2014
G.f.: 1 + Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - Ilya Gutkovskiy, May 18 2019

A184271 Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal binary arrays (n >= 1, k >= 1).

Original entry on oeis.org

2, 3, 3, 4, 7, 4, 6, 14, 14, 6, 8, 40, 64, 40, 8, 14, 108, 352, 352, 108, 14, 20, 362, 2192, 4156, 2192, 362, 20, 36, 1182, 14624, 52488, 52488, 14624, 1182, 36, 60, 4150, 99880, 699600, 1342208, 699600, 99880, 4150, 60, 108, 14602, 699252, 9587580, 35792568

Offset: 1

R. H. Hardin, Jan 10 2011

This is a 2-dimensional generalization of binary necklaces (A000031). A toroidal array or necklace can be defined either as an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns, or as a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns. - Gus Wiseman, Feb 04 2019

			      1     2        3           4            5             6              7
----------------------------------------------------------------------------
1:    2     3        4           6            8            14             20
2:    3     7       14          40          108           362           1182
3:    4    14       64         352         2192         14624          99880
4:    6    40      352        4156        52488        699600        9587580
5:    8   108     2192       52488      1342208      35792568      981706832
6:   14   362    14624      699600     35792568    1908897152   104715443852
7:   20  1182    99880     9587580    981706832  104715443852 11488774559744
8:   36  4150   699252   134223976  27487816992 5864063066500
9:   60 14602  4971184  1908881900 781874936816
10: 108 52588 35792568 27487869472
From _Gus Wiseman_, Feb 04 2019: (Start)
Inequivalent representatives of the T(2,3) = 14 toroidal necklaces:
  [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 1] [0 0 1] [0 0 1]
  [0 0 0] [0 0 1] [0 1 1] [1 1 1] [0 0 1] [0 1 0] [0 1 1]
.
  [0 0 1] [0 0 1] [0 0 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1]
  [1 0 1] [1 1 0] [1 1 1] [0 1 1] [1 0 1] [1 1 1] [1 1 1]
(End)

Alois P. Heinz, Antidiagonals n = 1..100, flattened (first 95 terms from R. H. Hardin)
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352, 2013 and J. Int. Seq. 16 (2013) #13.4.7 .
S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015 and J. Int. Seq. 18 (2015) # 15.8.3.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023.
Wikipedia, Pólya enumeration theorem

Columns 1-8 are A000031, A184264, A184265, A184266, A184267, A184268, A184269, A184270.
Main diagonal is A179043.
Cf. A001037 (binary Lyndon words), A008965, A323858, A323859 (binary toroidal necklaces of size n), A323861 (aperiodic version), A323865, A323870 (normal toroidal necklaces), A323872.

a[n_, k_] := Sum[If[Mod[n, c] == 0, Sum[If[Mod[k, d] == 0, EulerPhi[c] EulerPhi[d] 2^(n k/LCM[c, d]), 0], {d, 1, k}], 0], {c, 1, n}]/(n k)
(* second program *)
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
Table[Length[Select[Partition[#,n-k]&/@Tuples[{0,1},(n-k)*k],neckmatQ]],{n,8},{k,n-1}] (* Gus Wiseman, Feb 04 2019 *)

T(n,k) = (1/(nk))*Sum_{ c divides n } Sum_{ d divides k } phi(c)*phi(d)*2^(nk/lcm(c,d)), where phi is A000010 and lcm stands for least common multiple. - Stewart N. Ethier, Aug 24 2012

A329313 Length of the Lyndon factorization of the reversed binary expansion of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 2, 3, 1, 2, 1, 4, 1, 2, 2, 3, 1, 3, 2, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 2, 3, 2, 3, 2, 4, 1, 2, 3, 4, 1, 3, 2, 5, 1, 2, 2, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 2, 3, 2, 3, 2, 4, 1, 3, 3, 4, 2, 3, 2, 5, 1, 2, 2, 3, 1, 4, 3

Offset: 0

Gus Wiseman, Nov 11 2019

nonn

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

			The sequence of reversed binary expansions of the nonnegative integers together with their Lyndon factorizations begins:
   0:      () = ()
   1:     (1) = (1)
   2:    (01) = (01)
   3:    (11) = (1)(1)
   4:   (001) = (001)
   5:   (101) = (1)(01)
   6:   (011) = (011)
   7:   (111) = (1)(1)(1)
   8:  (0001) = (0001)
   9:  (1001) = (1)(001)
  10:  (0101) = (01)(01)
  11:  (1101) = (1)(1)(01)
  12:  (0011) = (0011)
  13:  (1011) = (1)(011)
  14:  (0111) = (0111)
  15:  (1111) = (1)(1)(1)(1)
  16: (00001) = (00001)
  17: (10001) = (1)(0001)
  18: (01001) = (01)(001)
  19: (11001) = (1)(1)(001)
  20: (00101) = (00101)

The non-reversed version is A211100.
Positions of 1's are A328596.
The "co" version is A329326.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose reversed binary expansion is a aperiodic are A328594.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A000031, A027375, A059966, A060223, A121016, A211097, A275692, A329131, A329314,  A329317, A329325.

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,#1]]&]]]];
Table[If[n==0,0,Length[lynfac[Reverse[IntegerDigits[n,2]]]]],{n,0,30}]

A329398 Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.

Original entry on oeis.org

1, 2, 4, 7, 12, 18, 28, 40, 57, 80, 110, 148, 200, 266, 348, 457, 592, 764, 978, 1248, 1580, 2000, 2508, 3142, 3913

Offset: 1

Gus Wiseman, Nov 13 2019

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 co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
A sequence of words is uniform if they all have the same length.
Conjecture: Also the number of compositions of n that are either weakly increasing or weakly decreasing. Hence a(n) = 2 * A000041(n) - A000005(n). - Gus Wiseman, Mar 05 2020

			The a(1) = 1 through a(6) = 18 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (112)   (41)     (42)
                    (211)   (113)    (51)
                    (1111)  (122)    (114)
                            (221)    (123)
                            (311)    (222)
                            (1112)   (321)
                            (2111)   (411)
                            (11111)  (1113)
                                     (1122)
                                     (2211)
                                     (3111)
                                     (11112)
                                     (21111)
                                     (111111)

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Lyndon compositions that are not weakly increasing are A329141.
Lyndon compositions whose reverse is not co-Lyndon are A329324.
Cf. A000740, A001037, A001523, A008965, A059204, A060223, A211100, A328596, A329312, A329318, A329396, A329397, A329399, A332578, A332669, A332834.

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,#]]&]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Length/@lynfac[#]&&SameQ@@Length/@colynfac[#]&]],{n,10}]

a(19)-a(25) from Robert Price, Jun 20 2021

A351017 Number of binary words of length n with all distinct run-lengths.

Original entry on oeis.org

1, 2, 2, 6, 6, 10, 22, 26, 38, 54, 114, 130, 202, 266, 386, 702, 870, 1234, 1702, 2354, 3110, 5502, 6594, 9514, 12586, 17522, 22610, 31206, 48630, 60922, 83734, 111482, 149750, 196086, 261618, 336850, 514810, 631946, 862130, 1116654, 1502982, 1916530, 2555734, 3242546

Offset: 0

Gus Wiseman, Feb 07 2022

nonn

			The a(0) = 1 through a(6) = 22 words:
  {}  0   00   000   0000   00000   000000
      1   11   001   0001   00001   000001
               011   0111   00011   000011
               100   1000   00111   000100
               110   1110   01111   000110
               111   1111   10000   001000
                            11000   001110
                            11100   001111
                            11110   011000
                            11111   011100
                                    011111
                                    100000
                                    100011
                                    100111
                                    110000
                                    110001
                                    110111
                                    111001
                                    111011
                                    111100
                                    111110
                                    111111

Using binary expansions instead of words gives A032020, ranked by A044813.
The version for partitions is A098859.
The complement is counted by twice A261982.
The version for compositions is A329739, for runs A351013.
For runs instead of run-lengths we have A351016, twice A351018.
The version for patterns is A351292, for runs A351200.
A000120 counts binary weight.
A001037 counts binary Lyndon words, necklaces A000031, aperiodic A027375.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329767 counts binary words by runs-resistance.
A351014 counts distinct runs in standard compositions.
A351204 counts partitions where every permutation has all distinct runs.
A351290 ranks compositions with all distinct runs.
Cf. A003242, A098504, A106356, A116608, A175413, A233564, A238130 or A238279, A328592, A334028, A350952.

Table[Length[Select[Tuples[{0,1},n],UnsameQ@@Length/@Split[#]&]],{n,0,10}]

from itertools import groupby, product
def adrl(s):
    runlens = [len(list(g)) for k, g in groupby(s)]
    return len(runlens) == len(set(runlens))
def a(n):
    if n == 0: return 1
    return 2*sum(adrl("1"+"".join(w)) for w in product("01", repeat=n-1))
print([a(n) for n in range(20)]) # Michael S. Branicky, Feb 08 2022

a(n>0) = 2 * A032020(n).

a(25)-a(32) from Michael S. Branicky, Feb 08 2022

More terms from David A. Corneth, Feb 08 2022 using data from A032020

A351016 Number of binary words of length n with all distinct runs.

Original entry on oeis.org

1, 2, 4, 6, 12, 18, 36, 54, 92, 154, 244, 382, 652, 994, 1572, 2414, 3884, 5810, 8996, 13406, 21148, 31194, 47508, 70086, 104844, 156738, 231044, 338998, 496300, 721042, 1064932, 1536550, 2232252, 3213338, 4628852, 6603758, 9554156, 13545314, 19354276

Offset: 0

Gus Wiseman, Feb 07 2022

nonn

These are binary words where the runs of zeros have all distinct lengths and the runs of ones also have all distinct lengths. For n > 0 this is twice the number of terms of A175413 that have n digits in binary.

			The a(0) = 1 through a(4) = 12 binary words:
  ()   0    00    000    0000
       1    01    001    0001
            10    011    0010
            11    100    0011
                  110    0100
                  111    0111
                         1000
                         1011
                         1100
                         1101
                         1110
                         1111
For example, the word (1,1,0,1) has three runs (1,1), (0), (1), which are all distinct, so is counted under a(4).

Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

The version for compositions is A351013, lengths A329739, ranked by A351290.
The version for [run-]lengths is A351017.
The version for expansions is A351018, lengths A032020, ranked by A175413.
The version for patterns is A351200, lengths A351292.
The version for permutations of prime factors is A351202.
A000120 counts binary weight.
A001037 counts binary Lyndon words, necklaces A000031, aperiodic A027375.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329767 counts binary words by runs-resistance.
A351014 counts distinct runs in standard compositions.
A351204 counts partitions whose permutations all have all distinct runs.
Cf. A003242, A098859, A106356, A116608, A238130 or A238279, A328592, A329738, A329745, A334028, A351201.

Table[Length[Select[Tuples[{0,1},n],UnsameQ@@Split[#]&]],{n,0,10}]

from itertools import groupby, product
def adr(s):
    runs = [(k, len(list(g))) for k, g in groupby(s)]
    return len(runs) == len(set(runs))
def a(n):
    if n == 0: return 1
    return 2*sum(adr("1"+"".join(w)) for w in product("01", repeat=n-1))
print([a(n) for n in range(20)]) # Michael S. Branicky, Feb 08 2022

a(n>0) = 2 * A351018(n).

a(25)-a(32) from Michael S. Branicky, Feb 08 2022

a(33)-a(38) from David A. Corneth, Feb 08 2022

A326774 For any number m, let m* be the bi-infinite string obtained by repetition of the binary representation of m; this sequence lists the numbers n such that for any k < n, n* does not equal k* up to a shift.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 11, 16, 17, 18, 19, 21, 23, 32, 33, 34, 35, 37, 38, 39, 43, 47, 64, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 77, 78, 79, 85, 87, 91, 95, 128, 129, 130, 131, 132, 133, 134, 135, 137, 138, 139, 140, 141, 142, 143, 146, 147, 149, 150, 151, 154

Offset: 0

Rémy Sigrist, Jul 27 2019

This sequence contains every power of 2.
No term belongs to A121016.
Every terms belongs to A004761.
For any k > 0, there are A001037(k) terms with binary length k.
From Gus Wiseman, Apr 19 2020: (Start)
Also numbers k such that the k-th composition in standard order (row k of A066099) is a co-Lyndon word (regular Lyndon words being A275692). For example, the sequence of all co-Lyndon words begins:
()            37: (3,2,1)         79: (3,1,1,1,1)
(1)           38: (3,1,2)         85: (2,2,2,1)
(2)           39: (3,1,1,1)       87: (2,2,1,1,1)
(3)           43: (2,2,1,1)       91: (2,1,2,1,1)
(2,1)         47: (2,1,1,1,1)     95: (2,1,1,1,1,1)
(4)           64: (7)            128: (8)
(3,1)         65: (6,1)          129: (7,1)
(2,1,1)       66: (5,2)          130: (6,2)
(5)           67: (5,1,1)        131: (6,1,1)
(4,1)         68: (4,3)          132: (5,3)
(3,2)         69: (4,2,1)        133: (5,2,1)
(3,1,1)       70: (4,1,2)        134: (5,1,2)
(2,2,1)       71: (4,1,1,1)      135: (5,1,1,1)
(2,1,1,1)     73: (3,3,1)        137: (4,3,1)
(6)           74: (3,2,2)        138: (4,2,2)
(5,1)         75: (3,2,1,1)      139: (4,2,1,1)
(4,2)         77: (3,1,2,1)      140: (4,1,3)
(4,1,1)       78: (3,1,1,2)      141: (4,1,2,1)
(End)

			3* = ...11... equals 1* = ...1..., so 3 is not a term.
6* = ...110... equals up to a shift 5* = ...101..., so 6 is not a term.
11* = ...1011... only equals up to a shift 13* = ...1101... and 14* = ...1110..., so 11 is a term.

Rémy Sigrist, Logarithmic scatterplot of the first differences of the terms < 2^24
Rémy Sigrist, PARI program for A326774

Cf. A001037, A004761, A065609, A121016.
Necklace compositions are counted by A008965.
Lyndon compositions are counted by A059966.
Length of Lyndon factorization of binary expansion is A211100.
Numbers whose reversed binary expansion is a necklace are A328595.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of Lyndon factorization of reversed binary expansion is A329313.
Length of co-Lyndon factorization of reversed binary expansion is A329326.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774 (this sequence).
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Reversed necklaces are A333943.
- Length of co-Lyndon factorization is A334029.
Cf. A000740, A034691, A060223, A269134, A292884, A328596.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Select[Range[0,100],colynQ[stc[#]]&] (* Gus Wiseman, Apr 19 2020 *)

PARI
```
See Links section.
```

A011260 Number of primitive polynomials of degree n over GF(2).

Original entry on oeis.org

1, 1, 2, 2, 6, 6, 18, 16, 48, 60, 176, 144, 630, 756, 1800, 2048, 7710, 7776, 27594, 24000, 84672, 120032, 356960, 276480, 1296000, 1719900, 4202496, 4741632, 18407808, 17820000, 69273666, 67108864, 211016256, 336849900, 929275200, 725594112, 3697909056

Offset: 1

N. J. A. Sloane

Elwyn R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
T. L. Booth, An analytical representation of signals in sequential networks, pp. 301-3240 of Proceedings of the Symposium on Mathematical Theory of Automata. New York, N.Y., 1962. Microwave Research Institute Symposia Series, Vol. XII; Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y. 1963 xix+640 pp. See p. 303.
Pingzhi Fan and Michael Darnell, Sequence Design for Communications Applications, Wiley, NY, 1996, Table 5.1, p. 118.
W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes. MIT Press, Cambridge, MA, 2nd edition, 1972, p. 476.
M. P. Ristenblatt, Pseudo-Random Binary Coded Waveforms, pp. 274-314 of R. S. Berkowitz, editor, Modern Radar, Wiley, NY, 1965; see p. 296.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Amiram Eldar, Table of n, a(n) for n = 1..1206 (terms 1..400 from David W. Wilson)
Joerg Arndt, Matters Computational (The Fxtbook).
Randolph Church, Tables of irreducible polynomials for the first four prime moduli, Annals Math., 36 (1935), 198-209.
Philip Koopman, Complete lists up to N=32.
Frank Ruskey, Primitive and Irreducible Polynomials [Wayback Machine link]
Eric Weisstein's World of Mathematics, Primitive Polynomial.
Tony F. Wu, Karthik Ganesan, Yunqing Alexander Hu, H.-S. Philip Wong, Simon Wong, and Subhasish Mitra, TPAD: Hardware Trojan Prevention and Detection for Trusted Integrated Circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 35, No. 4 (2016), pp. 521-534; arXiv preprint, arXiv:1505.02211 [cs.AR], 2015.

See A058947 for initial terms.

Cf. A000010, A000020, A001037, A027695.

Maple
```
with(numtheory): phi(2^n-1)/n;
```

Table[EulerPhi[(2^n - 1)]/n, {n, 1, 50}]

a(n)=eulerphi(2^n-1)/n \\ Hauke Worpel (thebigh(AT)outgun.com), Jun 10 2008

A333764 Numbers k such that the k-th composition in standard order is a co-necklace.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 15, 16, 17, 18, 19, 21, 23, 31, 32, 33, 34, 35, 36, 37, 38, 39, 42, 43, 45, 47, 63, 64, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 77, 78, 79, 85, 87, 91, 95, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140

Offset: 1

Gus Wiseman, Apr 12 2020

nonn

A co-necklace is a finite sequence that is lexicographically greater than or equal to any cyclic rotation.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions

			The sequence together with the corresponding co-necklaces begins:
    1: (1)             32: (6)               69: (4,2,1)
    2: (2)             33: (5,1)             70: (4,1,2)
    3: (1,1)           34: (4,2)             71: (4,1,1,1)
    4: (3)             35: (4,1,1)           73: (3,3,1)
    5: (2,1)           36: (3,3)             74: (3,2,2)
    7: (1,1,1)         37: (3,2,1)           75: (3,2,1,1)
    8: (4)             38: (3,1,2)           77: (3,1,2,1)
    9: (3,1)           39: (3,1,1,1)         78: (3,1,1,2)
   10: (2,2)           42: (2,2,2)           79: (3,1,1,1,1)
   11: (2,1,1)         43: (2,2,1,1)         85: (2,2,2,1)
   15: (1,1,1,1)       45: (2,1,2,1)         87: (2,2,1,1,1)
   16: (5)             47: (2,1,1,1,1)       91: (2,1,2,1,1)
   17: (4,1)           63: (1,1,1,1,1,1)     95: (2,1,1,1,1,1)
   18: (3,2)           64: (7)              127: (1,1,1,1,1,1,1)
   19: (3,1,1)         65: (6,1)            128: (8)
   21: (2,2,1)         66: (5,2)            129: (7,1)
   23: (2,1,1,1)       67: (5,1,1)          130: (6,2)
   31: (1,1,1,1,1)     68: (4,3)            131: (6,1,1)

The non-"co" version is A065609.
The reversed version is A328595.
Binary necklaces are A000031.
Necklace compositions are A008965.
Necklaces covering an initial interval are A019536.
Numbers whose prime signature is a necklace are A329138.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Length of Lyndon factorization is A329312.
- Rotational period is A333632.
- Reversed necklaces are A333943.
Cf. A000740, A001037, A027375, A059966, A211100, A302291, A328596, A329142, A333765, A333939, A333941.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
coneckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
Select[Range[100],coneckQ[stc[#]]&]

A329326 Length of the co-Lyndon factorization of the reversed binary expansion of n.

Original entry on oeis.org

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, 3, 3, 2, 6, 3, 4, 2, 5, 4, 3, 2

Offset: 1

Gus Wiseman, Nov 11 2019

nonn

First differs from A211100 at a(77) = 3, A211100(77) = 2. The reversed binary expansion of 77 is (1011001), with co-Lyndon factorization (10)(1100)(1), while the binary expansion is (1001101), with Lyndon factorization of (1)(001101).

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

			The reversed binary expansion of each positive integer together with their co-Lyndon factorizations begins:
   1:     (1) = (1)
   2:    (01) = (0)(1)
   3:    (11) = (1)(1)
   4:   (001) = (0)(0)(1)
   5:   (101) = (10)(1)
   6:   (011) = (0)(1)(1)
   7:   (111) = (1)(1)(1)
   8:  (0001) = (0)(0)(0)(1)
   9:  (1001) = (100)(1)
  10:  (0101) = (0)(10)(1)
  11:  (1101) = (110)(1)
  12:  (0011) = (0)(0)(1)(1)
  13:  (1011) = (10)(1)(1)
  14:  (0111) = (0)(1)(1)(1)
  15:  (1111) = (1)(1)(1)(1)
  16: (00001) = (0)(0)(0)(0)(1)
  17: (10001) = (1000)(1)
  18: (01001) = (0)(100)(1)
  19: (11001) = (1100)(1)
  20: (00101) = (0)(0)(10)(1)

The non-"co" version is A211100.
Positions of 2's are A329357.
Numbers whose binary expansion is co-Lyndon are A275692.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A328596, A329131, A329314, A329318, A329324, A329325.

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,#]]&]]];
Table[Length[colynfac[Reverse[IntegerDigits[n,2]]]],{n,100}]

cp's OEIS Frontend

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

A184271 Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal binary arrays (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A329313 Length of the Lyndon factorization of the reversed binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329398 Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A351017 Number of binary words of length n with all distinct run-lengths.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A351016 Number of binary words of length n with all distinct runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A326774 For any number m, let m* be the bi-infinite string obtained by repetition of the binary representation of m; this sequence lists the numbers n such that for any k < n, n* does not equal k* up to a shift.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs