The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A134457 a(n) = number of length-n binary strings with A006697(n) distinct substrings. 4
 1, 2, 2, 6, 8, 4, 18, 38, 48, 40, 16, 80, 210, 402, 644, 852, 928, 912, 704, 256, 1344, 3944, 9276, 19448, 37090, 65602, 107388, 160760, 220200 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS Here by "substring" one means a contiguous block within a string (often called "subword" or "factor"). LINKS Martin Fuller, Algorithm and table of n, c(n) for n = 1..69. Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8. Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, Comments on the previous paper. Antal Iványi, On the d-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput. 8 (1987), 69-90 (1988). Jeffrey Shallit, On the maximum number of distinct factors in a binary string, Graphs Combin. 9 (1993), no. 2, 197-200. EXAMPLE Table giving n, A006697(n) = maximal number of distinct substrings of a binary string of length n, a(n), c(n) = lexically first length-n binary string with A006697(n) distinct substrings. n A006697(n) a(n) c(n) 0 1 1 null 1 2 2 0 2 4 2 01 3 6 6 001 4 9 8 0010 5 13 4 00110 6 17 18 000110 7 22 38 0001011 8 28 48 00010110 9 35 40 000101100 10 43 16 0001011100 11 51 80 00001011100 12 60 210 000010011101 13 70 402 0000100110111 14 81 644 00001001101110 15 93 852 000010011010111 16 106 928 0000100110101110 17 120 912 00001001101011100 18 135 704 000010011010111000 19 151 256 0000100110101111000 20 167 1344 00000100110101111000 21 184 3944 000001000110101111001 22 202 9276 0000010001100101111010 23 221 19448 00000100011001010111101 24 241 37090 000001000110010101111010 25 262 65602 0000010001100101001111011 26 284 107388 00000100011001010011101111 27 307 160760 000001000110010100111011110 28 331 220200 0000010001100101001110101111 For (conjectural?) further values see the Martin Fuller link. CROSSREFS Cf. A006697, A134466(n) = decimal value of c(n) interpreted as a binary number. Sequence in context: A106166 A101343 A284748 * A326479 A306688 A092522 Adjacent sequences:  A134454 A134455 A134456 * A134458 A134459 A134460 KEYWORD nonn,more AUTHOR David W. Wilson, Dec 17 2007 EXTENSIONS Link to comments on history of the problem added by Jeffrey Shallit, May 08 2016 STATUS approved

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

Last modified March 29 05:39 EDT 2020. Contains 333105 sequences. (Running on oeis4.)