A134457 a(n) = number of length-n binary strings with A006697(n) distinct substrings.

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

Offset: 0

Author

David W. Wilson, Dec 17 2007

Keywords

• nonn
• more

Comments

Here by "substring" one means a contiguous block within a string (often called "subword" or "factor").

Examples

			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.
		

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.

Crossrefs

Cf. A006697, A134466(n) = decimal value of c(n) interpreted as a binary number.

Extensions

Link to comments on history of the problem added by Jeffrey Shallit, May 08 2016