A094913 extension

[Maximilian Hasler]

It also confirms the formula I gave,

A094913(n) = 2^(m+1)-2 + (n-m)(n-m+1)/2,

with

m = [ n+1-LambertW( 2^(n+1) * log(2) ) / log(2) ]
  = integer part of the solution to 2^x = n+1-x.

which is NOT based on the conjecture of Jovovic, but on the reasoning
that you can construct the word of length n such that it contains the
maximal possible number, equal to max( n-k+1 , 2^k ), of different
substrings of length k.
Maybe this was not very clear in my post, and also I shouldn't have
written it with "b" instead of "2"...

Maximilian Hasler

On Dec 17, 2007 11:19 AM, David W. Wilson <wilson.d at anseri.com> wrote:
>
>
>
>
> I wrote a brute-force program to compute A094913, which I ran over the
> weekend. The results are as follows:
>
>
>
> a(n) = maximum number of distinct substrings of a binary string of length n.
>
>
>
> b(n) = number of length-n binary strings with a(n) distinct substrings.
>
>
>
> c(n) = decimal value of d(n) interpreted as a binary number.
>
>
>
> d(n) = lexically first length-n binary string with a(n) distinct substrings.
>
>
>
>        n    a(n)    b(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
>
>
>
> Where both are defined, a(n) = A094913(n)+1. I would suggest replacing
> A094913 with a(n), since a(n) treats the empty string as a possible
> substring.
>
>
>
> The new elements a(19) through a(28) support Jovovic's conjecture that a(n)
> = A006697(n).