[seqfan] Re: The lex. earliest binary cube-free sequence

[David Wilson]

Obviously I computed this sequence in the straightforward way, at each step appending the smallest element that did not induce a cube, backtracking when necessary.

I computed 10200 elements, and did not observe backtracking over more than three contiguous elements in that range, so I think it astronomically unlikely that further computations would backtrack over most than 200 final elements resulting to invalidate the first 10000 elements.

I cannot prove that the elements of A282317 are correct, but I would be flabbergasted if they were not.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil
> Sloane
> Sent: Monday, May 01, 2017 12:14 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] The lex. earliest binary cube-free sequence
> 
> Consider the set S of all (0,1}-sequences that do not contain
> any cubes (no substring XXX). S is non-empty since it contains
> Thue-Morse A010060 and also A285196. S is totally ordered
> by lexicographic ordering. So by the Axiom of Choice there is a minimal
> element.
> 
> David Wilson's A282317 is defined to be this minimal element.
> 
> But there is no proof, as far as I know, that the terms
> that he has computed are correct (although they probably are correct.)
> His sequence begins
> 
> 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0,
> 1, ..
> 
> and he gives a b-file with 10000 terms.  One way that one might prove that
> his terms are correct would be to guess some kind of recurrence
> that matches his terms, and then to use this
> characterization to prove that the infinite extension is
> indeed cube-free and minimal.
> 
> This is the kind of question that we all deal with every day: given
> a sequence, find a rule that generates it. Here is a case when it would be
> really nice to find a rule!
> 
> Of course it could be that there is no rule, other than the definition.
> But that is unlikely, given that  “God does not play dice with the
> universe”.
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/