cp's OEIS Frontend

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

%I A366195 #44 Nov 12 2023 22:00:28
%S A366195 11,19,22,23,35,37,38,39,43,44,45,46,47,55,67,69,70,71,74,75,76,77,78,
%T A366195 79,83,86,87,88,89,90,91,92,93,94,95,103,110,111,131,133,134,135,137,
%U A366195 138,139,140,141,142,143,147,148,149,150,151,152,153,154,155,156
%N A366195 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 A366195 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 A366195 A328870 is a subsequence of this sequence.
%C A366195 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 A366195 Michael S. Branicky, <a href="/A366195/b366195.txt">Table of n, a(n) for n = 1..10000</a>
%H A366195 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</a>.
%e A366195 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 A366195 (Python)
%o A366195 def ok(n):
%o A366195     w = bin(n)[2:]
%o A366195     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 A366195 print([k for k in range(157) if ok(k)]) # _Michael S. Branicky_, Nov 09 2023
%Y A366195 Cf. A328870.
%K A366195 nonn,base
%O A366195 1,1
%A A366195 _Peter Kagey_, Nov 05 2023