[seqfan] Re: Distinct strings

[Allan Wechsler]

There are three or four sequences relevant to this idea already in OEIS, so
if this sequence is added, it would be good to include references to the
other sequences when appropriate.

A120004 is the basic idea: how many distinct numbers can be formed as
substrings of N?

A218978 is an irregular table explicitly listing the distinct substrings of
each number. This one has an intriguing graph, and makes interesting
listening too.

A120005 gives the smallest number with exactly n distinct substrings. The
given program is completely brute-force: it just considers every number,
counts the substrings, and checks to see if there are n of them. This is a
million times better than no program at all, but surely there is a better
way. This sequence only got to n=28 before whoever was running the code got
tired of waiting. Surely there is a better way! It sure looks like the
value is 10123456 for n=29.

An obvious sequence that underlies Éric's suggestion is a table read by
antidiagonals, where the function T(a,b) is the number of distinct
substrings of a ++ b, where ++ is the base-10 concatenation operator. I
think it starts: 1; 3,1; 3,2,1; 3,3,3,1 ... and this is already not in OEIS.

In fact, even the antidiagonal reading of the raw "++ table" seems to be
missing! 0; 10,1; 20,11,2 is already absent.

On Tue, Apr 2, 2019 at 11:10 AM Éric Angelini <bk263401 at skynet.be> wrote:

> Hello SeqFans,
> Could someone check and compute perhaps a few more terms
> (if this is of interest)?
> S = 1, 2, 222, 22, 2222, 3, 120, 10, 234, 24, 103, 112, 122, 100, 2345,
> 25, 1130, 102, 1345, 111, 2340, 1000,...
>
> We concatenate a(1) and a(2) to form 12.
> 12 produces 3 distinct strings: (12,1,2)
> We concatenate a(2) and a(3) to form 2222.
> 2222 produces 4 distinct strings: (222,222,22,2)
> We concatenate a(3) and a(4) to form 22222.
> 22222 produces 5 distinct strings: (22222,2222,222,22,2)
> We concatenate a(4) and a(5) to form 222222.
> 222222 produces 6 distinct strings: (222222,22222,2222,222,22,2)
> We concatenate a(5) and a(6) to form 22223.
> 22223 produces 9 distinct strings: (22223,2222,2223,222,223,22,23,2,3)
> etc.
>
> The rules:
> Lexico-first seq of distinct terms;
> Extend S with the smallest integer such that the new concatenation
> beats the previous one by the smallest possible margin (in terms of
> strings quantity).
>
> This might be not clear and I will explain with an example:
>
> Say we start T with:
>
> T = 1, 2, ...
> We could extend T with 10 as 210 produces 6 strings (210,21,10,2,1,0)
> -- and 6 strings "beats" the 3 strings of 12;
> What about extending T with 11 istead of 10? We have now 211 which
> produces 5 strings (211,21,11,2,1) which still beats the 3 strings of 12,
> but by a smaller margin (2 instead of 3);
> The best result comes from a(3) = 222 (and not 10 or 11) as 2222
> produces 4 strings (beats 3).
>
> BTW, 0 is a valid string, but not 01 (2019 would produce
> 2019,201,20,19,2,0,1,9 and not 019 or 01).
>
> I'm afraid the computing time will increase dramatically with the next
> terms
> (said my friend Solal Streeter who fought with his machine all night long
> !-)
> Best,
> É.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>