[seqfan] Re: Distinct strings

[Éric Angelini]

> it would be good to include references to the
> 
> other sequences when appropriate.

Yes, you're right Allan -- I will do (still
waiting for more terms computed by
my friend -- he has 45 by now!-)

Best,
É.



> Le 2 avr. 2019 à 23:45, Allan Wechsler <acwacw at gmail.com> a écrit :
> 
> 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/
>> 
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/