A366195 - OEIS

%I #44 Nov 12 2023 22:00:28

%S 11,19,22,23,35,37,38,39,43,44,45,46,47,55,67,69,70,71,74,75,76,77,78,

%T 79,83,86,87,88,89,90,91,92,93,94,95,103,110,111,131,133,134,135,137,

%U 138,139,140,141,142,143,147,148,149,150,151,152,153,154,155,156

%N Integers whose binary expansion has the property that there exists a length-k substring of bits in the expansion that is strictly lexicographically later than the first k bits.

%C These are numbers whose binary expansion corresponds to an invalid prefix of a Lyndon word on a two-letter alphabet. If the alphabet is {x, y}, where x < y, then taking the binary expansion of a(n) and mapping 1 to x and 0 to y results in a string that is not a prefix to any Lyndon word. Moreover, this sequence enumerates all strings starting with x that are not prefixes of Lyndon words on this alphabet.

%C A328870 is a subsequence of this sequence.

%C For k>=4, the number of k-bit terms in this sequence is 1,3,10,24,58,130,287,613,1302,2720,5655,11665,23969,...

%H Michael S. Branicky, <a href="/A366195/b366195.txt">Table of n, a(n) for n = 1..10000</a>

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

%e The binary expansion of a(3) = 22 is 10110, which has a length-2 substring ("11") which is strictly lexicographically later than the first 2 bits ("10"). This also means that xyxxy is not a prefix of any Lyndon word over the alphabet {x,y}.

%o (Python)

%o def ok(n):

%o     w = bin(n)[2:]

%o     return any(any(w[:k] < w[i:i+k] for i in range(1, len(w)-k+1)) for k in range(2, len(w)))

%o print([k for k in range(157) if ok(k)]) # _Michael S. Branicky_, Nov 09 2023

%Y Cf. A328870.

%K nonn,base

%O 1,1

%A _Peter Kagey_, Nov 05 2023