login
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.
2
11, 19, 22, 23, 35, 37, 38, 39, 43, 44, 45, 46, 47, 55, 67, 69, 70, 71, 74, 75, 76, 77, 78, 79, 83, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 103, 110, 111, 131, 133, 134, 135, 137, 138, 139, 140, 141, 142, 143, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156
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
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
Cf. A328870.
Sequence in context: A344936 A238247 A004750 * A328870 A244287 A065126
KEYWORD
nonn,base
AUTHOR
Peter Kagey, Nov 05 2023
STATUS
approved