%I #12 Jan 13 2023 13:21:02
%S 1,2,4,6,9,12,16,21,26,32,39,46,54,63,72,82,93,105,117,130,144,159,
%T 175,191,208,226,245,264,284,305,327
%N Maximum number of positive numbers represented by substrings of an n-bit number's binary representation
%C Equivalently, maximum number of distinct substrings starting with a "1" digit.
%H 2008/9 British Mathematical Olympiad Round 2, <a href="http://www.bmoc.maths.org/home/bmo2-2009.pdf">Problem 4</a>, Jan 29 2009.
%o (Python)
%o from itertools import product
%o def s(w):
%o return set(w[i:j+1] for i in range(len(w)) if w[i] != "0" for j in range(i, len(w)))
%o def a(n):
%o return max(len(s("1"+"".join(b))) for b in product("01", repeat=n-1))
%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jan 13 2023
%Y Cf. A078822, A112509, A112510, A112511, A122953, A156023, A156024, A156025.
%Y Equals A112509(n)-1 for n >= 2.
%K nonn,base,more
%O 1,2
%A _Joseph Myers_, Feb 01 2009
|