login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A156022
Maximum number of positive numbers represented by substrings of an n-bit number's binary representation
6
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
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
Equals A112509(n)-1 for n >= 2.
Sequence in context: A194250 A024610 A022778 * A224809 A327094 A048171
KEYWORD
nonn,base,more
AUTHOR
Joseph Myers, Feb 01 2009
STATUS
approved