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, 350, 374, 398, 423, 449, 476, 503, 531, 560, 590, 621, 653, 686, 719, 753, 788, 824, 861, 898, 936, 976, 1016, 1057, 1099, 1142

Offset: 1

Author

Joseph Myers, Feb 01 2009

Keywords

• nonn
• base

Comments

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

Links

• Martin Fuller, Table of n, a(n) for n = 1..80
• 2008/9 British Mathematical Olympiad Round 2, Problem 4, Jan 29 2009.

Crossrefs

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

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

Programs

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

Extensions

a(32) onwards from Martin Fuller, Jul 24 2025