login
Numbers whose bijective base-2 representation is a Lyndon word.
2

%I #35 Mar 28 2021 17:01:27

%S 1,2,4,8,10,16,18,22,32,34,36,38,42,46,64,66,68,70,74,76,78,86,94,128,

%T 130,132,134,136,138,140,142,146,148,150,154,156,158,170,174,182,190,

%U 256,258,260,262,264,266,268,270,274,276,278,280,282,284,286,292,294,298,300,302,308

%N Numbers whose bijective base-2 representation is a Lyndon word.

%C A Lyndon word is a word which is lexicographically smaller than all its nontrivial rotations.

%C From the Chen-Fox-Lyndon theorem, every word can be written in a unique way as a concatenation of a nonincreasing sequence of Lyndon words. Since each natural number has a unique string representation in bijective bases, it can also be written exactly one way as a concatenation of these numbers in nonincreasing lexicographic order, in bijective base-2.

%H Harald Korneliussen, <a href="/A339608/b339608.txt">Table of n, a(n) for n = 1..20000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Bijective_numeration">Bijective numeration</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lyndon_word#Standard_factorization">Standard factorization of a Lyndon word</a>

%F Observation: a(n) = 2*A326774(n-1), n >= 2. (At least for the terms from the Data section). - _Omar E. Pol_, Dec 09 2020

%F A007931(a(n)) = A102659(n). - _Alois P. Heinz_, Dec 09 2020

%F a(n) = A329327(n) - 1. - _Harald Korneliussen_, Mar 02 2021

%e 1 and 2 are in this sequence, since their bijective base-2 representations are also just "1" and "2", and words of just one letter have no nontrivial rotations.

%e 3 is not in this sequence, since written in bijective base-2 it becomes "11", which is equal to its single nontrivial rotation.

%e 108 is not in this sequence, since in bijective base-2 it becomes "212212", which is larger than two of its nontrivial rotations (both equal to "122122"). However, "212212" can be uniquely split into the lexicographically nonincreasing sequence of Lyndon words "2", "122" and "12", corresponding to 2, 10 and 4 in this sequence.

%Y Cf. A007931, A102659, A326774, A329327.

%K nonn,base

%O 1,2

%A _Harald Korneliussen_, Dec 09 2020