A156022 Maximum number of positive numbers represented by substrings of an n-bit number's binary representation

1, 2, 4, 6, 9, 12, 16, 21, 26, 32, 39, 46, 54, 63, 72, 82, 93, 105, 117, 130, 144, 159, 175, 191, 208, 226, 245, 264, 284, 305, 327

Offset

1,2

Comments

Equivalently, maximum number of distinct substrings starting with a "1" digit.

Links

Table of n, a(n) for n=1..31.

2008/9 British Mathematical Olympiad Round 2, Problem 4, Jan 29 2009.

Prog

(Python)
from itertools import product
def s(w):
    return set(w[i:j+1] for i in range(len(w)) if w[i] != "0" for j in range(i, len(w)))
def a(n):
    return max(len(s("1"+"".join(b))) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jan 13 2023

Crossrefs

Cf. A078822, A112509, A112510, A112511, A122953, A156023, A156024, A156025.

Equals A112509(n)-1 for n >= 2.

Sequence in context: A194250 A024610 A022778 * A224809 A327094 A048171

Adjacent sequences: A156019 A156020 A156021 * A156023 A156024 A156025

Keyword

nonn,base,more

Author

Joseph Myers, Feb 01 2009

Status

approved