[seqfan] Re: Distinct strings

[Éric Angelini]

Hello Lars,
I was indeed not clear:

> 3120 gives 15	terms 0,1,2,3,10,12,20,30,31,32,120,310,312,320,3120.

... no, 3120 doesn't give 320 -- as the strings
cannot be split into one or more "omponents".

Best,
É.



> Le 4 avril 2019 à 14:23, Lars Blomberg <larsl.blomberg at comhem.se> a écrit :
> 
> 
> For a(7) I get 100, not 120.
> 
> 3120 gives 15	terms 0,1,2,3,10,12,20,30,31,32,120,310,312,320,3120.
> 3100 gives 10 terms 0,1,3,10,30,31,100,300,310,3100.
> And 10 is 1 more than the previous count.
> I must be misunderstanding something here.
> Regards
> Lars B
> 
> -----Ursprungligt meddelande-----
> Från: SeqFan <seqfan-bounces at list.seqfan.eu> För Éric Angelini
> Skickat: den 3 april 2019 18:09
> Till: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Ämne: [seqfan] Re: Distinct strings
> 
> 
> > 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/
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/
> 
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/