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-10 of 24 results. Next

A275692 Numbers k such that every rotation of the binary digits of k is less than k.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 32, 40, 48, 50, 52, 56, 58, 60, 62, 64, 72, 80, 84, 96, 98, 100, 104, 106, 108, 112, 114, 116, 118, 120, 122, 124, 126, 128, 144, 160, 164, 168, 192, 194, 196, 200, 202, 208, 210, 212, 216, 218, 224, 226, 228
Offset: 1

Views

Author

Robert Israel, Aug 05 2016

Keywords

Comments

0, and terms of A065609 that are not in A121016.
Number of terms with d binary digits is A001037(d).
Take the binary representation of a(n), reverse it, add 1 to each digit. The result is the decimal representation of A102659(n).
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 Lyndon word. For example, the sequence of all Lyndon words begins:
0: () 52: (1,2,3) 118: (1,1,2,1,2)
1: (1) 56: (1,1,4) 120: (1,1,1,4)
2: (2) 58: (1,1,2,2) 122: (1,1,1,2,2)
4: (3) 60: (1,1,1,3) 124: (1,1,1,1,3)
6: (1,2) 62: (1,1,1,1,2) 126: (1,1,1,1,1,2)
8: (4) 64: (7) 128: (8)
12: (1,3) 72: (3,4) 144: (3,5)
14: (1,1,2) 80: (2,5) 160: (2,6)
16: (5) 84: (2,2,3) 164: (2,3,3)
20: (2,3) 96: (1,6) 168: (2,2,4)
24: (1,4) 98: (1,4,2) 192: (1,7)
26: (1,2,2) 100: (1,3,3) 194: (1,5,2)
28: (1,1,3) 104: (1,2,4) 196: (1,4,3)
30: (1,1,1,2) 106: (1,2,2,2) 200: (1,3,4)
32: (6) 108: (1,2,1,3) 202: (1,3,2,2)
40: (2,4) 112: (1,1,5) 208: (1,2,5)
48: (1,5) 114: (1,1,3,2) 210: (1,2,3,2)
50: (1,3,2) 116: (1,1,2,3) 212: (1,2,2,3)
(End)

Examples

			6 is in the sequence because its binary representation 110 is greater than all the rotations 011 and 101.
10 is not in the sequence because its binary representation 1010 is unchanged under rotation by 2 places.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
    1:       1 ~ {1}
    2:      10 ~ {2}
    4:     100 ~ {3}
    6:     110 ~ {2,3}
    8:    1000 ~ {4}
   12:    1100 ~ {3,4}
   14:    1110 ~ {2,3,4}
   16:   10000 ~ {5}
   20:   10100 ~ {3,5}
   24:   11000 ~ {4,5}
   26:   11010 ~ {2,4,5}
   28:   11100 ~ {3,4,5}
   30:   11110 ~ {2,3,4,5}
   32:  100000 ~ {6}
   40:  101000 ~ {4,6}
   48:  110000 ~ {5,6}
   50:  110010 ~ {2,5,6}
   52:  110100 ~ {3,5,6}
   56:  111000 ~ {4,5,6}
   58:  111010 ~ {2,4,5,6}
(End)

Links

Crossrefs

A similar concept is A328596.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose reversed binary expansion is a necklace are A328595.
Binary necklaces are A000031.
Binary Lyndon words are A001037.
Lyndon compositions are A059966.
Length of Lyndon factorization of binary expansion is A211100.
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.
Cf. A000031, A000740, A008965, A027375, A102659, A121016.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692 (this sequence).
- Co-Lyndon compositions are A326774.
- 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.
Cf. A034691, A060223, A124767, A269134, A292884.

Programs

  • Maple
    filter:= proc(n) local L, k;
  L:= convert(convert(n,binary),string);
  for k from 1 to length(L)-1 do
    if lexorder(L,StringTools:-Rotate(L,k)) then return false fi;
  od;
  true
end proc:
select(filter, [$0..1000]);
  • Mathematica
    filterQ[n_] := Module[{bits, rr}, bits = IntegerDigits[n, 2]; rr = NestList[RotateRight, bits, Length[bits]-1] // Rest; AllTrue[rr, FromDigits[#, 2] < n&]];
Select[Range[0, 1000], filterQ] (* Jean-François Alcover, Apr 29 2019 *)
  • Python
    def ok(n):
    b = bin(n)[2:]
    return all(b[i:] + b[:i] < b for i in range(1, len(b)))
print([k for k in range(230) if ok(k)]) # Michael S. Branicky, May 26 2022

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

A329312 Length of the co-Lyndon factorization of the binary expansion of n.

Original entry on oeis.org

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, 2, 3, 2, 5, 1, 2, 1, 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: 1

Views

Author

Gus Wiseman, Nov 10 2019

Keywords

Comments

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 a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).
Also the length of the Lyndon factorization of the inverted binary expansion of n, where the inverted digits are 1 minus the binary digits.

Examples

			The binary indices of 1..20 together with their co-Lyndon factorizations are:
   1:     (1) = (1)
   2:    (10) = (10)
   3:    (11) = (1)(1)
   4:   (100) = (100)
   5:   (101) = (10)(1)
   6:   (110) = (110)
   7:   (111) = (1)(1)(1)
   8:  (1000) = (1000)
   9:  (1001) = (100)(1)
  10:  (1010) = (10)(10)
  11:  (1011) = (10)(1)(1)
  12:  (1100) = (1100)
  13:  (1101) = (110)(1)
  14:  (1110) = (1110)
  15:  (1111) = (1)(1)(1)(1)
  16: (10000) = (10000)
  17: (10001) = (1000)(1)
  18: (10010) = (100)(10)
  19: (10011) = (100)(1)(1)
  20: (10100) = (10100)

Crossrefs

The non-"co" version is A211100.
Positions of 1's are A275692.
The reversed version is A329326.
Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A329131, A329314, A329318, A329324, A329325.

Programs

  • Mathematica
    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[IntegerDigits[n,2]]],{n,100}]

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

Views

Author

Gus Wiseman, Nov 11 2019

Keywords

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

Examples

			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)

Crossrefs

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.

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

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

Views

Author

Rémy Sigrist, Jul 27 2019

Keywords

Comments

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:
0: () 37: (3,2,1) 79: (3,1,1,1,1)
1: (1) 38: (3,1,2) 85: (2,2,2,1)
2: (2) 39: (3,1,1,1) 87: (2,2,1,1,1)
4: (3) 43: (2,2,1,1) 91: (2,1,2,1,1)
5: (2,1) 47: (2,1,1,1,1) 95: (2,1,1,1,1,1)
8: (4) 64: (7) 128: (8)
9: (3,1) 65: (6,1) 129: (7,1)
11: (2,1,1) 66: (5,2) 130: (6,2)
16: (5) 67: (5,1,1) 131: (6,1,1)
17: (4,1) 68: (4,3) 132: (5,3)
18: (3,2) 69: (4,2,1) 133: (5,2,1)
19: (3,1,1) 70: (4,1,2) 134: (5,1,2)
21: (2,2,1) 71: (4,1,1,1) 135: (5,1,1,1)
23: (2,1,1,1) 73: (3,3,1) 137: (4,3,1)
32: (6) 74: (3,2,2) 138: (4,2,2)
33: (5,1) 75: (3,2,1,1) 139: (4,2,1,1)
34: (4,2) 77: (3,1,2,1) 140: (4,1,3)
35: (4,1,1) 78: (3,1,1,2) 141: (4,1,2,1)
(End)

Examples

			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.

Links

Crossrefs

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.

Programs

  • Mathematica
    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.

A333632 Rotational period of the k-th composition in standard order; a(0) = 0.

Original entry on oeis.org

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

Views

Author

Gus Wiseman, Apr 12 2020

Keywords

Comments

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, 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.

Examples

			The a(299) = 5 rotations:
  (1,1,3,2,2)
  (1,3,2,2,1)
  (3,2,2,1,1)
  (2,2,1,1,3)
  (2,1,1,3,2)
The a(9933) = 4 rotations:
  (1,2,1,3,1,2,1,3)
  (1,3,1,2,1,3,1,2)
  (2,1,3,1,2,1,3,1)
  (3,1,2,1,3,1,2,1)

Crossrefs

Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
The version for binary expansion is A302291.
Numbers whose prime signature is aperiodic are A329139.
Compositions by number of distinct rotations are A333941.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Equal 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.
- Rotational period is A333632 (this sequence).
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A328595, A328596, A329312, A329313, A329326.

Programs

  • Mathematica
    stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[Array[RotateRight[stc[n],#]&,DigitCount[n,2,1]]]],{n,0,100}]

Formula

a(n) = A000120(n)/A138904(n) = A302291(n) - A023416(n)/A138904(n).

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

A138904 Number of rotational symmetries in the binary expansion of a number.

Original entry on oeis.org

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

Views

Author

Max Sills, Apr 03 2008, Apr 04 2008

Keywords

Comments

Mersenne numbers of form (2^n - 1) have n rotational symmetries.
For prime length binary expansions these are the only nontrivial symmetries.
For composite length expansions it seems that when the number of symmetries is nontrivial it is equal to a factor of the length. We're working on an explicit formula.
Discovered in the context of random circulant matrices, examining if there's a correlation between degrees of freedom and number of symmetries in the first row.
When combined with A138954, these two sequences should give a full account of the number of redundant rows in a circulant square matrix with at most two distinct values, where a(n) is the encoding of the first row of the matrix into binary such that value a = 1 and value b = 0.
Discovered on the night of Apr 02, 2008 by Maxwell Sills and Gary Doran.
Conjecture: For binary expansions of length n, there are d(n) distinct values that will show up as symmetries, where d is the divisor function. The symmetry values will be precisely the divisors of n.
Example: for binary expansions of length 12, one sees that d(12) = 6 distinct values show up as symmetries (1, 2, 3, 4, 6, 12).
Conjecture: For numbers whose binary expansion has length n which has proper divisors which are all coprime: There will be only one number of length n with n symmetries. That number is 2^n - 1. For each proper divisor d (excluding 1), you can generate all numbers of length n that have n/d symmetries like so: (2^0 + 2^d + 2^2d ... 2^(n-d)) * a, where 2^(d-1) <= a < (2^d) - 1. The rest of the expansions of length n will have only the trivial symmetry.
Also the number of rotational symmetries of the n-th composition in standard order (graded reverse-lexicographic). This composition (row n of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. - Gus Wiseman, Apr 19 2020
From Gus Wiseman, Apr 19 2020: (Start)
Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Period of binary expansion is A302291.
Compositions by sum and number of distinct rotations are A333941.
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.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A328595, A328596, A329312, A329313, A329326.
(End).

Examples

			a(10) = 2 because the binary expansion of 10 is 1010 and it has two rotational symmetries (including identity).

Links

Crossrefs

Cf. A136441, A138954.

Programs

  • Mathematica
    Table[IntegerLength[n,2]/Length[Union[Array[RotateRight[IntegerDigits[n,2],#]&,IntegerLength[n,2]]]],{n,100}] (* Gus Wiseman, Apr 19 2020 *)

Formula

a(n) = A070939(n)/A302291(n) = A000120(n)/A333632(n). - Gus Wiseman, Apr 19 2020

A329395 Numbers whose binary expansion without the most significant (first) digit has Lyndon and co-Lyndon factorizations of equal lengths.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 10, 13, 15, 16, 22, 25, 31, 32, 36, 42, 46, 49, 53, 59, 63, 64, 76, 82, 94, 97, 109, 115, 127, 128, 136, 148, 156, 162, 166, 169, 170, 172, 181, 182, 190, 193, 201, 202, 211, 213, 214, 217, 221, 227, 235, 247, 255, 256, 280, 292, 306, 308
Offset: 1

Views

Author

Gus Wiseman, Nov 13 2019

Keywords

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 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).
Conjecture: also numbers k such that the k-th composition in standard order (A066099) is a palindrome, cf. A025065, A242414, A317085, A317086, A317087, A335373. - Gus Wiseman, Jun 06 2020

Examples

			The sequence of terms together with their trimmed binary expansions and their co-Lyndon and Lyndon factorizations begins:
   1:      () =               0 = 0
   2:     (0) =             (0) = (0)
   3:     (1) =             (1) = (1)
   4:    (00) =          (0)(0) = (0)(0)
   7:    (11) =          (1)(1) = (1)(1)
   8:   (000) =       (0)(0)(0) = (0)(0)(0)
  10:   (010) =         (0)(10) = (01)(0)
  13:   (101) =         (10)(1) = (1)(01)
  15:   (111) =       (1)(1)(1) = (1)(1)(1)
  16:  (0000) =    (0)(0)(0)(0) = (0)(0)(0)(0)
  22:  (0110) =        (0)(110) = (011)(0)
  25:  (1001) =        (100)(1) = (1)(001)
  31:  (1111) =    (1)(1)(1)(1) = (1)(1)(1)(1)
  32: (00000) = (0)(0)(0)(0)(0) = (0)(0)(0)(0)(0)
  36: (00100) =     (0)(0)(100) = (001)(0)(0)
  42: (01010) =     (0)(10)(10) = (01)(01)(0)
  46: (01110) =       (0)(1110) = (0111)(0)
  49: (10001) =       (1000)(1) = (1)(0001)
  53: (10101) =     (10)(10)(1) = (1)(01)(01)
  59: (11011) =     (110)(1)(1) = (1)(1)(011)
  63: (11111) = (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)

Crossrefs

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Cf. A001037, A060223, A102659, A211100, A329131, A329312, A329313, A329318, A329326, A329394, A329398.
Cf. A329358, A329399, A329400, A329401.

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, #]]&]]]];
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[Rest[IntegerDigits[#,2]]]]==Length[colynfac[Rest[IntegerDigits[#,2]]]]&]

A281013 Tetrangle T(n,k,i) = i-th part of k-th prime composition of n.

Original entry on oeis.org

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

Views

Author

Gus Wiseman, Jan 12 2017

Keywords

Comments

The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling them together. Every finite positive integer sequence has a unique *-factorization using prime compositions P = {(1), (2), (21), (3), (211), ...}. See A060223 and A228369 for details.
These are co-Lyndon compositions, ordered first by sum and then lexicographically. - Gus Wiseman, Nov 15 2019

Examples

			The prime factorization of (1, 1, 4, 2, 3, 1, 5, 5) is: (11423155) = (1)*(1)*(5)*(5)*(4231). The prime factorizations of the initial terms of A000002 are:
             (1) = (1)
            (12) = (1)*(2)
           (122) = (1)*(2)*(2)
          (1221) = (1)*(221)
         (12211) = (1)*(2211)
        (122112) = (1)*(2)*(2211)
       (1221121) = (1)*(221121)
      (12211212) = (1)*(2)*(221121)
     (122112122) = (1)*(2)*(2)*(221121)
    (1221121221) = (1)*(221)*(221121)
   (12211212212) = (1)*(2)*(221)*(221121)
  (122112122122) = (1)*(2)*(2)*(221)*(221121).
Read as a sequence:
(1), (2), (21), (3), (211), (31), (4), (2111), (221), (311), (32), (41), (5).
Read as a triangle:
(1)
(2)
(21), (3)
(211), (31), (4)
(2111), (221), (311), (32), (41), (5).
Read as a sequence of triangles:
1    2    2 1    2 1 1    2 1 1 1    2 1 1 1 1    2 1 1 1 1 1
          3      3 1      2 2 1      2 2 1 1      2 1 2 1 1
                 4        3 1 1      3 1 1 1      2 2 1 1 1
                          3 2        3 1 2        2 2 2 1
                          4 1        3 2 1        3 1 1 1 1
                          5          4 1 1        3 1 1 2
                                     4 2          3 1 2 1
                                     5 1          3 2 1 1
                                     6            3 2 2
                                                  3 3 1
                                                  4 1 1 1
                                                  4 1 2
                                                  4 2 1
                                                  4 3
                                                  5 1 1
                                                  5 2
                                                  6 1
                                                  7.

Crossrefs

Cf. A000740, A215474, A228369, A277427.
The binary version is A329318.
The binary non-"co" version is A102659.
A sequence listing all Lyndon compositions is A294859.
Numbers whose binary expansion is co-Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Binary Lyndon words are A001037.
Lyndon compositions are A059966.
Normal Lyndon words are A060223.
Cf. A211097, A211100, A296372, A296373, A298941, A329131, A329312, A329313, A329314, A329324, A329326.

Programs

  • Mathematica
    colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],colynQ],lexsort],{n,5}] (* Gus Wiseman, Nov 15 2019 *)

Formula

Row lengths are A059966(n) = number of prime compositions of n.
Showing 1-10 of 24 results. Next

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

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