OFFSET
1,2
COMMENTS
The number of substrings in k is A141297(k) and the maximum possible in n bits is A094913(n), so that a(n) is the smallest k for which A141297(k) = A094913(n).
a(n) is an n bit number since the maximum A094913(n) is strictly increasing.
When computing a(n), one may speed the calculations considerably by "stopping early" when the maximum value seen equals A094913(n) = A006697(n)-1; see Allouche and Shallit, p. 6. - Michael S. Branicky, Dec 31 2025
LINKS
J.-P. Allouche and Jeffrey Shallit, On the subword complexity of the fixed point of a -> aab, b -> b, and generalizations, arXiv preprint arXiv:1605.02361 [math.CO], 2016.
EXAMPLE
For n = 4: the least 4-bit number which has the maximum number of distinct (nonempty) substrings in the binary representation is k = (9)_10 = (1001)_2 with 8 substrings {0,1,00,01,10,001,100,1001}, thus a(4) = 9.
MATHEMATICA
a[n_] := Module[{k1 = If[n == 1, 0, 2^(n-1)], k2 = 2^n-1, kmax, f, fmax = -1}, Do[f = -1 + CountDistinct[Subsequences[IntegerDigits[k, 2]]]; If[f > fmax, fmax = f; kmax = k], {k, k1, k2}]; kmax]; Array[a, 15] (* Amiram Eldar, Dec 21 2025 *)
PROG
(Python)
from itertools import product
def f(w): # A141297 for binary string w
m = len(w)
return len(set(w[i:j] for i in range(m) for j in range(i+1, m+1)))
def a(n):
if n == 1: return 0
mx, agmx = -1, None
for w in product("01", repeat=n-1):
w = "1" + "".join(w)
v = f(w)
if v > mx:
mx, argmx = v, int(w, 2)
# CAN STOP EARLY HERE: if mx == A006697(n) - 1: return argmx
return argmx
print([a(n) for n in range(1, 17)]) # Michael S. Branicky, Dec 31 2025
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Ctibor O. Zizka, Dec 20 2025
EXTENSIONS
a(25)-a(35) from Michael S. Branicky, Dec 31 2025
STATUS
approved