A094913 extension

[Martin Fuller]

Maximilian's formula works up to n=69 at least.

The following algorithm usually finds a maximal solution quite quickly:
1. Work out Maximilian's m (the shortest subword length where each
subword can be distinct).
2. Depth first search, digit by digit, checking that all subwords of
length m are distinct.
3. Check that all the shorter words are present when length n is
reached. If not, go back into the depth first search.
4. All the longer words are guaranteed distinct by the construction
method.

The program is currently checking n=70.  I suspect it wastes a lot of
time on solutions which are missing the subword 111111.  An improvement
to step 3 could make a big difference.

Here are the least solutions for n up to 69:

1 0
2 01
3 001
4 0010
5 00110
6 000110
7 0001011
8 00010110
9 000101100
10 0001011100
11 00001011100
12 000010011101
13 0000100110111
14 00001001101110
15 000010011010111
16 0000100110101110
17 00001001101011100
18 000010011010111000
19 0000100110101111000
20 00000100110101111000
21 000001000110101111001
22 0000010001100101111010
23 00000100011001010111101
24 000001000110010101111010
25 0000010001100101001111011
26 00000100011001010011101111
27 000001000110010100111011110
28 0000010001100101001110101111
29 00000100011001010011101011110
30 000001000110010100111010111100
31 0000010001100101001110101101111
32 00000100011001010011101011011110
33 000001000110010100111010110111100
34 0000010001100101001110101101111000
35 00000100011001010011101011011110000
36 000001000110010100111010110111110000
37 0000001000110010100111010110111110000
38 00000010000110010100111010110111110001
39 000000100001100010100111010110111110010
40 0000001000011000101001011011100111110101
41 00000010000110001010010011101011011111001
42 000000100001100010100100111010110111110010
43 0000001000011000101000111010110111110010011
44 00000010000110001010001110010011010111110110
45 000000100001100010100011100100110101101111101
46 0000001000011000101000111001001101010111110110
47 00000010000110001010001110010011010101101111101
48 000000100001100010100011100100101100110111110101
49 0000001000011000101000111001001011001101011111011
50 00000010000110001010001110010010110011010111110110
51 000000100001100010100011100100101100110101011111011
52 0000001000011000101000111001001011001101010111110110
53 00000010000110001010001110010010110011010101110111110
54 000000100001100010100011100100101100110101011101111100
55 0000001000011000101000111001001011001101001111101110101
56 00000010000110001010001110010010110011010011111010111011
57 000000100001100010100011100100101100110100111110101110110
58 0000001000011000101000111001001011001101001111010111011111
59 00000010000110001010001110010010110011010011110101110111110
60 000000100001100010100011100100101100110100111101010111011111
61 0000001000011000101000111001001011001101001111010101110111110
62 00000010000110001010001110010010110011010011110101011101111100
63 000000100001100010100011100100101100110100111101010111011011111
64 0000001000011000101000111001001011001101001111010101110110111110
65 00000010000110001010001110010010110011010011110101011101101111100
66 000000100001100010100011100100101100110100111101010111011011111000
67 0000001000011000101000111001001011001101001111010101110110111110000
68 00000010000110001010001110010010110011010011110101011101101111100000
69
000000100001100010100011100100101100110100111101010111011011111100000

Martin Fuller

PS How many length 2^k+k-1 words are there which include all the
subwords of length k?  David W. Wilson's data shows the series starts
1, 2, 4, 16, 256 (from A094913 n=0, 2, 5, 10, 19) which appears to grow
rapidly.  Assuming it stays positive, Maximilian's formula will hold
true for all n=2^k+k-1.

--- Maximilian Hasler <maximilian.hasler at gmail.com> wrote:

> 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