OFFSET
1,1
COMMENTS
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.
A328870 is a subsequence of this sequence.
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,...
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..10000
Wikipedia, Lyndon word.
EXAMPLE
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}.
PROG
(Python)
def ok(n):
w = bin(n)[2:]
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)))
print([k for k in range(157) if ok(k)]) # Michael S. Branicky, Nov 09 2023
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Peter Kagey, Nov 05 2023
STATUS
approved