[seqfan] Re: More about lex earliest cubefree 0,1 sequence

M. F. Hasler seqfan at hasler.fr
Sat May 20 23:38:33 CEST 2017

On Sat, May 20, 2017 at 5:47 PM, Neil Sloane <njasloane at gmail.com> wrote:

> The entry A282317 gives 10000 terms, starting
> 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, ...
> but there is no proof that this is correct.
I claim that the first 6 terms are correct, (...)
> The question is, can this argument be extended to prove that more
> terms of A282317 are correct?  That is, let W denote the first k terms of
> A282317, can we construct an infinite cubefree sequence that begins with
> W?  That would prove the first k terms of A282317 are correct.

We also know that A282317 is "minimal": by construction (I refer to the
computed terms) it is the lexicographically smallest cubefree sequence that
can be constructed in a precise greedy way guaranteeing minimality, which
does not seem to require backtracking:
Essentially, append at each step the largest possible part of the existing
sequence; if a cube would appear then "increase" it (in the sense of a
binary word) at the point where the earliest cube would end and discard the
rest, until it's cubefree.

If this never results in a maximal cubefree word (A282133), then it is
infinite and also correct (since minimal and cubefree by construction).

So it would also be sufficient to show that the words constructed in that
way (S.S'.1 where S' is the longest possible truncation of S so that S.S'.1
is cubefree) are never maximal.


More information about the SeqFan mailing list