The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A112509 Maximum number of numbers represented by substrings of an n-bit 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 stand-alone binary representations and the reversal of substrings is not permitted. LINKS Table of n, a(n) for n=1..31. 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 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.). 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=n-1)) print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jan 13 2023 CROSSREFS Cf. A112510 (least n-bit number for which this maximum occurs), A112511 (greatest n-bit number for which this maximum occurs). Cf. A078822, A122953, A156022, A156023, A156024, A156025. Equals A156022(n)+1 for n >= 2. [From Joseph Myers, Feb 01 2009] Sequence in context: A195311 A184013 A057672 * A296846 A173137 A310020 Adjacent sequences: A112506 A112507 A112508 * A112510 A112511 A112512 KEYWORD nonn,base,more AUTHOR Rick L. Shepherd, Sep 09 2005 EXTENSIONS a(21) to a(31) from Joseph Myers, Feb 01 2009 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 19 14:41 EDT 2024. Contains 374410 sequences. (Running on oeis4.)