cp's OEIS Frontend

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

%I A112509 #20 Jul 24 2025 16:55:03
%S A112509 1,3,5,7,10,13,17,22,27,33,40,47,55,64,73,83,94,106,118,131,145,160,
%T A112509 176,192,209,227,246,265,285,306,328,351,375,399,424,450,477,504,532,
%U A112509 561,591,622,654,687,720,754,789,825,862,899,937,977,1017,1058,1100,1143
%N A112509 Maximum number of numbers represented by substrings of an n-bit number's binary representation.
%C A112509 Substrings must be contiguous, they are treated as stand-alone binary representations and the reversal of substrings is not permitted.
%H A112509 Martin Fuller, <a href="/A112509/b112509.txt">Table of n, a(n) for n = 1..80</a>
%H A112509 2008/9 British Mathematical Olympiad Round 2, <a href="http://www.bmoc.maths.org/home/bmo2-2009.pdf">Problem 4</a>, Jan 29 2009.
%e A112509 To see why a(4)=7 (and A112510(4)=12 and A112511(4)=14), consider all numbers whose binary representations require exactly 4 bits: 1000, 1001, 1010, 1011, 1100, 1101, 1110 and 1111. For each of these binary representations in turn, we find the nonnegative integers represented by all of its contiguous substrings. We count these distinct integer values (putting the count in {}s):
%e A112509 1000: any 0, either 00, or 000 -> 0, 1 -> 1, 10 -> 2, 100 -> 4, 1000 -> 8 {5};
%e A112509 1001: either 0, or 00 -> 0, either 1, 01, or 001 -> 1, 10 -> 2, 100 -> 4, 1001 -> 9 {5};
%e A112509 (For brevity, binary substrings are shown below only if they produce values not shown yet.)
%e A112509 1010: 0, 1, 2, 101 -> 5, 1010 -> 10 {5};
%e A112509 1011: 0, 1, 2, 11 -> 3, 5, 1011 -> 11 {6};
%e A112509 1100: 0, 1, 2, 3, 4, 110 -> 6, 1100 -> 12 {7};
%e A112509 1101: 0, 1, 2, 3, 5, 6, 1101 -> 13 {7};
%e A112509 1110: 0, 1, 2, 3, 6, 111 -> 7, 1110 -> 14 {7};
%e A112509 1111: 1, 3, 7, 1111 -> 15 {4}.
%e A112509 Because the maximum number of distinct integer values {in brackets} is 7, a(4)=7. The smallest 4-bit number for which 7 distinct values are found is 12, so A112510(4)=12. The largest 4-bit number for which 7 are found is 14, so A112511(4)=14. (For n=4 the count is a(n)=7 also for all values (only one, 13, here) between A112510(n) and A112511(n). This is not the case in general.).
%o A112509 (Python)
%o A112509 from itertools import product
%o A112509 def c(w):
%o A112509     return len(set(w[i:j+1] for i in range(len(w)) if w[i] != "0" for j in range(i,len(w)))) + int("0" in w)
%o A112509 def a(n):
%o A112509     return max(c("1"+"".join(b)) for b in product("01", repeat=n-1))
%o A112509 print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jan 13 2023
%Y A112509 Cf. A112510 (least n-bit number for which this maximum occurs), A112511 (greatest n-bit number for which this maximum occurs).
%Y A112509 Cf. A078822, A122953, A156022, A156023, A156024, A156025. Equals A156022(n)+1 for n >= 2. [From _Joseph Myers_, Feb 01 2009]
%K A112509 nonn,base
%O A112509 1,2
%A A112509 _Rick L. Shepherd_, Sep 09 2005
%E A112509 a(21) to a(31) from _Joseph Myers_, Feb 01 2009
%E A112509 a(32) onwards from _Martin Fuller_, Jul 24 2025