cp's OEIS Frontend

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

%I A156022 #18 Jul 24 2025 21:02:27
%S A156022 1,2,4,6,9,12,16,21,26,32,39,46,54,63,72,82,93,105,117,130,144,159,
%T A156022 175,191,208,226,245,264,284,305,327,350,374,398,423,449,476,503,531,
%U A156022 560,590,621,653,686,719,753,788,824,861,898,936,976,1016,1057,1099,1142
%N A156022 Maximum number of positive numbers represented by substrings of an n-bit number's binary representation.
%C A156022 Equivalently, maximum number of distinct substrings starting with a "1" digit.
%H A156022 Martin Fuller, <a href="/A156022/b156022.txt">Table of n, a(n) for n = 1..80</a>
%H A156022 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 A156022 (Python)
%o A156022 from itertools import product
%o A156022 def s(w):
%o A156022     return set(w[i:j+1] for i in range(len(w)) if w[i] != "0" for j in range(i, len(w)))
%o A156022 def a(n):
%o A156022     return max(len(s("1"+"".join(b))) for b in product("01", repeat=n-1))
%o A156022 print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jan 13 2023
%Y A156022 Cf. A078822, A112509, A112510, A112511, A122953, A156023, A156024, A156025.
%Y A156022 Equals A112509(n)-1 for n >= 2.
%K A156022 nonn,base
%O A156022 1,2
%A A156022 _Joseph Myers_, Feb 01 2009
%E A156022 a(32) onwards from _Martin Fuller_, Jul 24 2025