

A112509


Maximum number of numbers represented by substrings of an nbit number's binary representation.


6



1, 3, 5, 7, 10, 13, 17, 22, 27, 33, 40, 47, 55, 64, 73, 83, 94, 106, 118, 131, 145, 160, 176, 192, 209, 227, 246, 265, 285, 306, 328
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Substrings must be contiguous, they are treated as standalone binary representations and the reversal of substrings is not permitted.


LINKS

2008/9 British Mathematical Olympiad Round 2, Problem 4, Jan 29 2009.


EXAMPLE

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):
1000: any 0, either 00, or 000 > 0, 1 > 1, 10 > 2, 100 > 4, 1000 > 8 {5};
1001: either 0, or 00 > 0, either 1, 01, or 001 > 1, 10 > 2, 100 > 4, 1001 > 9 {5};
(For brevity, binary substrings are shown below only if they produce values not shown yet.)
1010: 0, 1, 2, 101 > 5, 1010 > 10 {5};
1011: 0, 1, 2, 11 > 3, 5, 1011 > 11 {6};
1100: 0, 1, 2, 3, 4, 110 > 6, 1100 > 12 {7};
1101: 0, 1, 2, 3, 5, 6, 1101 > 13 {7};
1110: 0, 1, 2, 3, 6, 111 > 7, 1110 > 14 {7};
1111: 1, 3, 7, 1111 > 15 {4}.
Because the maximum number of distinct integer values {in brackets} is 7, a(4)=7. The smallest 4bit number for which 7 distinct values are found is 12, so A112510(4)=12. The largest 4bit 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.).


PROG

(Python)
from itertools import product
def c(w):
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)
def a(n):
return max(c("1"+"".join(b)) for b in product("01", repeat=n1))


CROSSREFS

Cf. A112510 (least nbit number for which this maximum occurs), A112511 (greatest nbit number for which this maximum occurs).


KEYWORD

nonn,base,more


AUTHOR



EXTENSIONS



STATUS

approved



