Last bubbles?

 

I really like the Bubble sort despite (or because of?) its inefficiency and slowness — and was looking for more sequences to send to the OEIS.

There is S hereunder, of course, computed with the help of Nicolas Graner:

"Number of swaps needed to bubble-sort the US English number names (no swap involves spaces or hyphens)" :

S = 4, 3, 2, 8, 1, 3, 1, 5, 2, 4, 2, 4, 9, 16, 16, 10, 13, 17, 11, 13, 5, 21, 14, 34, 21, 25, 16, 30, 29, 27, 3, 20, 11, 32, 18, 23, 12, 28, 27, 25, 0, 15, 7, 25, 11, 17, 8, 22, 20, 21, 1, 13, 7, 25, 10, 15, 7, 21, 17, 16, 2, 18, 12, 31, 18, 21, 11, 26, 25, 23, 6, 22, 15, 35, 22, 25, 16, 29, 30, 28, 2, 14, 8, 26, 13, 18, 8, 22, 19, 17, 4, 16, 10, 30, 15, 22, 12, 24, 26, 21, 28, ... 

(S was proposed to the OEIS a few minutes ago).

I was also looking for T, an infinite non-trivial sequence of digits obeying this rule:

"A digit k in the sequence indicates that the set of (k+1) digits coming immediately after k needs k swaps to be bubble-sorted in descending order".

After a few trials, nightmares and errors, I came up with this (explanation below, blue tag):

T = 0, 1, 1, 2, 3, 0, 4, 0, 4, 0, 5, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 3, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 1, 0, 5, 0, 0, 0, 0, 0, 1, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 1, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 3, 1, 4, 5, 0, 1, 0, 2. <—— stuck!

[Ouch! Is there a backtracking technique which would allow T to be extended to infinity? We neither would want to be stuck at some point, of course, or enter into a loop.]

Explanations so far:

a(1) = 0 because zero never "lies" – indeed, the 0-set of numbers is always well-ordered:

T = 0, 1, 1, 2, 3, 0, 4, 0, 4, 0, 5, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, ...

a(2) = 1 says that the hereunder aqua set of 2-numbers needs exactly 1 swap (to show its elements in descending order):

T = 0, 1, 1, 2, 3, 0, 4, 0, 4, 0, 5, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, ...

a(3) = 1 says that the hereunder aqua set of 2-numbers needs exactly 1 swap (to show its elements in descending order):

T = 0, 1, 1, 2, 3, 0, 4, 0, 4, 0, 5, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, ...

a(4) = 2 says that the hereunder aqua set of 3-numbers needs exactly 2 swaps (to show its elements in descending order):

T = 0, 1, 1, 2, 3, 0, 4, 0, 4, 0, 5, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, ...

a(11) = 5 says that the hereunder aqua set of 6-numbers needs exactly 5 swaps (to show its elements in descending order):

T = 0, 1, 1, 2, 3, 0, 4, 0, 4, 0, 5, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, ...

Etc.

My problem

What is, exactly, a "non-trivial sequence"? The hereunder U and V are obviously dull:

U = 0, 0, 0, 0, 0, 0, 0, 0, ...

V = 1, 0, 1, 0, 1, 0, 1, 0, ...

But what about W, X, Y, Z?

W = 1, 0, 1, 0, 2, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 2, 0, 0, ...

X = 1, 0, 1, 0, 1, 0, 2, 1, 0, 2, 1, 0,  2, 1, 0,  2, 1, 0,  2, 1, 0,  2, 1, 0, ...

Y = 1, 0, 3, 0, 0, 0, 3, 0, 0, 1, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 1, 3, 0, 0, 1, ...

Z = 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, ...

Mmmmh, it seems that there are sets of digits that can be repeated infinitely – like the last one [1, 0, 3, 2].

This suggests N

 "Numbers which, repeatedly concatenated, produce a sequence where any digit k indicates that the set of (k+1) digits coming immediately after k needs k swaps to be bubble-sorted in descending order". 

I have no precise idea about which numbers should be present in N, but I guess the hereunder ones would belong to N:

N = 0, 10, 102, 200, 210, 1010, 1032, 2001, 2103, 3000, 3210, ...

Is it possible that the above sequence T that I was looking for would simply be made of (non repeated) terms of N, properly ordered and "linked"? (answer: no!-)

Anyway, this was fun to explore! Long live the Bubble sort!

____________________

Next morning update

Jean-Marc Falcoz was quick to compute the 566 terms of N < 10000000 with their according graph:

N = 0,10,30,60,102,103,200,203,210,310,320,600,606,660,1010,1032,1040,1055,1062,1065,1454,2003,2005,2032,2042,2052,2055,2065,2103,2106,2203,2204,2205,3000,3030,3040,3043,3053,3055,3065,3200,3210,3220,3304,3305,4004,4005,4010,4030,4045,4145,4220,4330,4400,4540,4541,5105,5106,5200,5205,5206,5220,5305,5306,5330,5400,5404,5414,5510,5520,5530,6060,6210,6510,6520,6530,9000,10200,10202,10432,10600,20010,20043,20050,20210,20432,21020,21043,22043,30004,30007,30433,30533,30633,30733,32004,32104,32204,33043,33053,33063,33073,33304,33305,33306,33307,40000,40544,40600,40644,40744,43000,43200,43210,43220,43330,44054,44064,44074,44405,44406,44407,50200,53330,54440,60006,60007,60010,60040,60066,63330,64440,66000,66006,66600,73000,73330,74440,76000,101010,101030,102002,102102,102103,102204,103000,103010,103032,103040,103102,103103,103204,104002,105432,108000,200200,200210,200543,200700,203203,204102,204103,205432,210200,210210,210303,210310,210400,210543,220410,220543,230404,300010,300054,300060,301010,303030,303210,304010,304042,310210,310310,320054,320320,320410,321030,321054,322054,400005,400009,400210,401030,404230,405444,406444,407444,408444,409444,410220,410320,423040,430005,432005,432105,432205,440544,440644,440744,440844,440944,444054,444064,444074,444084,444094,444405,444406,444407,444408,444409,500000,506555,507555,508000,508555,509555,540000,543000,543200,543210,543220,544440,550655,550755,550855,550955,555065,555075,555085,555095,555506,555507,555508,555509,600600,600700,603000,606060,606606,644440,655550,660660,700200,700600,744440,755550,800008,800009,800010,800050,844440,855550,880000,940000,944440,955550,980000,1010200,1010205,1010405,1010500,1020010,1020040,1020440,1020510,1022042,1022044,1030002,1030202,1032004,1032032,1032052,1032105,1033105,1034005,1040000,1040200,1040432,1040440,1040510,1042002,1042032,1042052,1042105,1043105,1044002,1044004,1050010,1050040,1050202,1050505,1051032,1051033,1051042,1051043,1051134,1052004,1052054,1053054,1065432,1134105,1341051,2001010,2001040,2002104,2002204,2003000,2003050,2003203,2003205,2004003,2004010,2004103,2004105,2006543,2009000,2021030,2021050,2032003,2032032,2032042,2032103,2032104,2032203,2032204,2033205,2042002,2042032,2042042,2042102,2042203,2042204,2043205,2044002,2044004,2044010,2044102,2051010,2052003,2052033,2052043,2052103,2052104,2053054,2054105,2065432,2102204,2103000,2103020,2103203,2103205,2104043,2104200,2104203,2104205,2104400,2105020,2105103,2105104,2106543,2203203,2203204,2204200,2204203,2204204,2204210,2204400,2204410,2206543,2305054,3000200,3000210,3000654,3000800,3020210,3040440,3050200,3050505,3050542,3054105,3054205,3105103,3105104,3200320,3200400,3200410,3200654,3203200,3203210,3203220,3204220,3205200,3205203,3205204,3205210,3210320,3210404,3210420,3210510,3210654,3220320,3220420,3220654,3310510,3320520,3400510,3410511,4000010,4000065,4000070,4002104,4002204,4003200,4004104,4004204,4005103,4010200,4010204,4010404,4010500,4020010,4030404,4040500,4043210,4044010,4044030,4050040,4051010,4102204,4103200,4104400,4105113,4105200,4105205,4105305,4200210,4200220,4203210,4203220,4204220,4204400,4205210,4205305,4210220,4210510,4220320,4220420,4230505,4300065,4310510,4320065,4320520,4321040,4321065,4322065,4400210,4400220,4400410,4400420,4401020,4401040,4403040,4410220,5000006,5001010,5004010,5004040,5020030,5020210,5050510,5050530,5051050,5053050,5054230,5065555,5075555,5085555,5095555,5101020,5101040,5103210,5103310,5103400,5104210,5104310,5105050,5113410,5200320,5200410,5203320,5204320,5205410,5210320,5210420,5305050,5305410,5305420,5400006,5410520,5410530,5420530,5423050,5430006,5432006,5432106,5432206,5506555,5507555,5508555,5509555,5550655,5550755,5550855,5550955,5555065,5555075,5555085,5555095,5555506,5555507,5555508,5555509,6000000,6076666,6086666,6096666,6500000,6540000,6543000,6543200,6543210,6543220,6555550,6607666,6608666,6609666,6660766,6660866,6660966,6666076,6666086,6666096,6666607,6666608,6666609,7009000,7040000,7555550,7666660,8003000,8555550,8666660,9000200,9000700,9555550,9666660.

(Google translation after the French text)

JMF

Quelque remarques (a few remarks) :

– Chaque fois qu’un nombre est dans N, le nombre répété l’est aussi.

– (Whenever a number is in N, so is the repeated number.)

Par exemple 1454 appartient à N, donc 14541454 aussi, ainsi que 145414541454, etc.

(For instance 1454 belongs to N, so 14541454 too, as well as 145414541454, etc.)

– Dans N, il y a des sous-suites, menant elles-mêmes à des sous-suites, par exemple :

(– In N, there are subsequences, themselves leading to subsequences, for example:)

10

210

3210

43210

543210

6543210

76543210

876543210

9876543210

... sont tous dans N, et chacune de leurs permutations circulaires aussi.

(... are all in N, and so are each of their circular permutations.)

Par exemple pour 6543210, les nombres ci-dessous sont dans N :

(For example for 6543210, the numbers below are in N:)

6543210

5432106

4321065

3210654

2106543

1065432

... et même 0654321 qui y serait si un nombre pouvait commencer par 0.

(... and even 0654321 which would be there if a number could start with 0.)

Voici des sous-suites, menant elles-mêmes à des sous-suites, menant elles-mêmes à des sous-suites :

(Here are subsequences, themselves leading to subsequences, themselves leading to subsequences:)

10

210

3210

...

menant par exemple à

(leading for instance to)

3210

2103

1032

0321

...

menant par exemple à

(leading for instance to)

2103

21032103

210321032103

– L’association du 6 et du 0 fonctionne bien, et on retrouve beaucoup de nombres composés uniquement de 0 et de 6 dans N :

(– The association of 6 and 0 works well, and we find many numbers composed only of 0 and 6 in N:)

60,6060,606060,... 600,600600,600600600, ... 606, 606606, 606606606,... 660, 660660, 660660660,...

____________________

ÉA

Waoow, merci pour tout, Jean-Marc, quelles merveilles !