A329131 -id:A329131 - cp's OEIS frontend

A348268 Mapping between Lyndon factorization and prime factorization.

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

A334298 Numbers whose prime signature is a reversed Lyndon word.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16, 17, 19, 20, 23, 24, 25, 27, 28, 29, 31, 32, 37, 40, 41, 43, 44, 45, 47, 48, 49, 52, 53, 56, 59, 60, 61, 63, 64, 67, 68, 71, 72, 73, 76, 79, 80, 81, 83, 84, 88, 89, 92, 96, 97, 99, 101, 103, 104, 107, 109, 112, 113, 116

Offset: 1

Gus Wiseman, Jun 10 2020

nonn

A Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations.

A number's prime signature is the sequence of positive exponents in its prime factorization.

			The prime signature of 4200 is (3,1,2,1), which is a reversed Lyndon word, so 4200 is in the sequence.
The sequence of terms together with their prime indices begins:
   1: {}           23: {9}            48: {1,1,1,1,2}
   2: {1}          24: {1,1,1,2}      49: {4,4}
   3: {2}          25: {3,3}          52: {1,1,6}
   4: {1,1}        27: {2,2,2}        53: {16}
   5: {3}          28: {1,1,4}        56: {1,1,1,4}
   7: {4}          29: {10}           59: {17}
   8: {1,1,1}      31: {11}           60: {1,1,2,3}
   9: {2,2}        32: {1,1,1,1,1}    61: {18}
  11: {5}          37: {12}           63: {2,2,4}
  12: {1,1,2}      40: {1,1,1,3}      64: {1,1,1,1,1,1}
  13: {6}          41: {13}           67: {19}
  16: {1,1,1,1}    43: {14}           68: {1,1,7}
  17: {7}          44: {1,1,5}        71: {20}
  19: {8}          45: {2,2,3}        72: {1,1,1,2,2}
  20: {1,1,3}      47: {15}           73: {21}

The non-reversed version is A329131.
Lyndon compositions are A059966.
Prime signature is A124010.
Numbers with strictly decreasing prime multiplicities are A304686.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose prime signature is a necklace are A329138.
Numbers whose prime signature is aperiodic are A329139.
Cf. A000031, A000740, A000961, A001037, A025487, A027375, A097318, A112798, A118914, A304678, A318731, A329140, A329142.

lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
Select[Range[100],lynQ[Reverse[Last/@If[#==1,{},FactorInteger[#]]]]&]

cp's OEIS Frontend

A348268 Mapping between Lyndon factorization and prime factorization.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula