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

Author

Thomas Scheuerle, Oct 09 2021

Keywords

• nonn
• base

Comments

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.

Examples

			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.
		

Links

• 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

Crossrefs

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

Programs

MATLAB

% See Scheuerle link.

Formula

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