A328595 -id:A328595 - cp's OEIS frontend

A329357 Numbers whose reversed binary expansion has co-Lyndon factorization of length 2.

2, 3, 5, 9, 11, 17, 19, 23, 33, 35, 37, 39, 43, 47, 65, 67, 69, 71, 75, 79, 83, 87, 95, 129, 131, 133, 135, 137, 139, 143, 147, 149, 151, 155, 159, 163, 167, 171, 175, 183, 191, 257, 259, 261, 263, 265, 267, 271, 275, 277, 279, 283, 287, 291, 293, 295, 299

Offset: 1

Gus Wiseman, Nov 12 2019

nonn

First differs from A329327 in lacking 77 and having 83.

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

			The reversed binary expansion of each term together with their co-Lyndon factorizations:
   2:      (01) = (0)(1)
   3:      (11) = (1)(1)
   5:     (101) = (10)(1)
   9:    (1001) = (100)(1)
  11:    (1101) = (110)(1)
  17:   (10001) = (1000)(1)
  19:   (11001) = (1100)(1)
  23:   (11101) = (1110)(1)
  33:  (100001) = (10000)(1)
  35:  (110001) = (11000)(1)
  37:  (101001) = (10100)(1)
  39:  (111001) = (11100)(1)
  43:  (110101) = (11010)(1)
  47:  (111101) = (11110)(1)
  65: (1000001) = (100000)(1)
  67: (1100001) = (110000)(1)
  69: (1010001) = (101000)(1)
  71: (1110001) = (111000)(1)
  75: (1101001) = (110100)(1)
  79: (1111001) = (111100)(1)

Positions of 2's in A329326.
Binary co-Lyndon words are counted by A001037 and ranked by A329318.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A060223, A102659, A211097, A211100, A275692, A328594, A328595, A328596, A329131, A329313, A329314, A329325, A329359.

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

A348268 Mapping between Lyndon factorization and prime factorization.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 11, 10, 9, 12, 13, 14, 17, 16, 19, 22, 15, 20, 29, 18, 21, 24, 23, 26, 37, 28, 31, 34, 41, 32, 43, 38, 33, 44, 25, 30, 35, 40, 53, 58, 27, 36, 67, 42, 51, 48, 47, 46, 39, 52, 61, 74, 49, 56, 59, 62, 73, 68, 71, 82, 79, 64, 83, 86, 57, 76, 55, 66, 77

Offset: 0

Thomas Scheuerle, Oct 09 2021

A Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations.
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).
We use Lyndon factorization on the reversed order binary expansion of n, then we use the mapping from Lyndon words (A328596(k) reversed binary expansion) to positive integers that have no divisors other than 1 and itself (A008578(k+1)). a(n) has factors in A008578 as the binary expansion of n has in A328596.

			We map Lyndon-words to positive integers that have no divisors other than 1 and itself: [] -> 1, 1 -> 2, 01 -> 3, 001 -> 5, 011 -> 7, 0001 -> 11, ...
9 is in reversed order binary: 1001, has the factors (1)(001) -> a(9) = 2*5 = 10.
10 is in reversed order binary: 0101, has the factors (01)(01) -> a(10) = 3*3 = 9.

Thomas Scheuerle, Table of n, a(n) for n = 0..5000
Thomas Scheuerle, Program (MATLAB)
Index entries for sequences that are permutations of the natural numbers

Cf. A329313, A328596, A008578, A329399, A000961, A328595, A328595.

MATLAB
```
% See Scheuerle link.
```

a(Lyndonproduct(n,m)) = a(n)*a(m).
a(1 + 2*n)/a(n) = 2.
all a(A329399(n)) are in A000961 (powers of primes).
all a(A328595(n)) (reversed binary expansion is a necklace) are in A329131 (prime signature is a Lyndon word).

A329367 Numbers whose binary expansion, without the most significant digit, is not a necklace.

Original entry on oeis.org

6, 10, 12, 13, 14, 18, 20, 22, 24, 25, 26, 27, 28, 29, 30, 34, 36, 38, 40, 41, 42, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 66, 68, 70, 72, 74, 76, 78, 80, 81, 82, 83, 84, 86, 88, 89, 90, 92, 93, 94, 96, 97, 98, 99, 100, 101, 102

Offset: 1

Gus Wiseman, Nov 15 2019

nonn

A necklace is a finite sequence that is lexicographically minimal among all of its cyclic rotations.

			The sequence of terms together with their binary expansions begins:
   6: (1,1,0)
  10: (1,0,1,0)
  12: (1,1,0,0)
  13: (1,1,0,1)
  14: (1,1,1,0)
  18: (1,0,0,1,0)
  20: (1,0,1,0,0)
  22: (1,0,1,1,0)
  24: (1,1,0,0,0)
  25: (1,1,0,0,1)
  26: (1,1,0,1,0)
  27: (1,1,0,1,1)
  28: (1,1,1,0,0)
  29: (1,1,1,0,1)
  30: (1,1,1,1,0)
  34: (1,0,0,0,1,0)
  36: (1,0,0,1,0,0)
  38: (1,0,0,1,1,0)
  40: (1,0,1,0,0,0)
  41: (1,0,1,0,0,1)

The complement is A328668.
The version involving all digits is A062289.
The reverse version is A328607.
Binary necklaces are A000031.
Necklace compositions are A008965.
Numbers whose binary expansion is a necklace are A275692.
Numbers whose reversed binary expansion is a necklace are A328595.
Cf. A000120, A001037, A003714, A065609, A069010, A257739, A328596.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Select[Range[2,100],!neckQ[Rest[IntegerDigits[#,2]]]&]

cp's OEIS Frontend

A329357 Numbers whose reversed binary expansion has co-Lyndon factorization of length 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A348268 Mapping between Lyndon factorization and prime factorization.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

A329367 Numbers whose binary expansion, without the most significant digit, is not a necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica