A094913 extension
Maximilian Hasler
maximilian.hasler at gmail.com
Mon Dec 17 20:42:57 CET 2007
PS: sorry for the typo, should read "min" (in the text)
Also, I wanted to comment on your suggestion :
even if I agree that the empty substring should have been included (as
I wrote earlier), I think we should not change this >6 year old
sequence (insofar more as the "new" sequence already exists - I'm
confident that we'll soon have a proof for a(n)+1 = A006697(n));
maybe just add "nonempty" in the definition and if needed, write a comment
%C A094913 It would be more natural to include the empty substring,
which would result in the sequence b(n)=a(n)+1 ; all values computed
so far confirm the conjecture that a(n)+1 = A006697(n)."
Maximilian Hasler
On Dec 17, 2007 3:30 PM, Maximilian Hasler <maximilian.hasler at gmail.com> wrote:
> 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).
>
--
Maximilian F. Hasler (Maximilian.Hasler(AT)gmail.com)
More information about the SeqFan
mailing list