[seqfan] Re: Distinct strings

[Lars Blomberg]

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/