On behalf of Gilles Best, É. On January 18th 2017 at 14:30, <Eric.Angelini@kntv.be<mailto:Eric.Angelini@kntv.be>> wrote: - what is the lexicographically first binary cubefree seq? Dear cube-free sequence fans (I am impressed to see some great names in the list!) Many thanks for your already deep answers. The construction of the first elements of the sequence is indeed straightforward, and one finds: AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B ... (where I used A and B instead of your 0 and 1). A kind of chaotic pattern appears, and one may thus define a more compact notation: 1 = AAB AAB AB AAB AAB B 2 = AAB AAB AB AAB AB B 3 = AAB AAB AB AAB B 4 = AAB AAB AB B 5 = AAB AB AAB AAB B 6 = AB AAB AAB B 7 = AB AAB B which allows me to give you now more than 15000 terms : 112 113 114 113 114 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 ... There again appears a clear structure, but it is obviously non periodic (cube-free), and the property of being the lexicographically first sequence seems to generate more chaos than for Prouhet-Thue-Morse. It can be shown that these first terms are correct, i.e., that they will never be modified by some subsequent term inducing a very long cube. [My naive way of proving so was to note that the substring BBAABB never appears, therefore that one may glue the infinite Prouhet-Thue-Morse sequence (starting from its 22nd term, i.e., precisely BBAABB) at a point, and this proves that the backtracking cannot spoil what we already computed.] Can Esposito-Farèse report the maximum amount of backtracking that he needed Well, I needed to program a specific routine to answer this question, as my method of construction did not work letter by letter (to increase its speed, and I therefore needed to backtrack more sometimes). When I work letter by letter, it seems that the backtracking never exceeds 3. It simply happens when one tries to add an extra A at the end of a string of the form ...ABB, and that this generates a cube (sometimes very long!). One should then a priori try to add a B instead, but ...ABBB is also forbidden. Therefore one has to go back to the previous ...A and replace it by ...B. [I checked that only on the first thousand of terms, and not on the full result above.] Many questions may be asked. One of the most immediate would be: Can it be proven that this sequence will never become equivalent to another known cube-free sequence (Prouhet-Thue-Morse, Kolakoski, Stewart's choral, ...) after a given term? A probably more difficult question: Does this sequence have any mathematical interest? (besides the fact that it also gives the lexicographically last cube-free sequence by replacing A <--> B ;-) Looking forward to your insights; sincerely, G.E-F à+ É. Catapulté de mon aPhone