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

M. F. Hasler seqfan at hasler.fr
Tue May 2 23:09:18 CEST 2017


On Mon, May 1, 2017 at 12:13 AM, Neil Sloane <njasloane at gmail.com> wrote:

> Consider the set S of all (0,1}-sequences that do not contain
> any cubes (no substring XXX).
> David Wilson's A282317 is defined to be this minimal element.
> 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, .


I think it could be interesting to add the sequences:
indices of 1's in A282317 <https://oeis.org/A282317>:
2,5,7,10,13,14,17,20,22,25

Or, this shifted by 1 (i.e., using offset 1 in  A282317):
3,6,8,11,14,15,18,21,23,26

Since the alphabet consists in only 2 symbols, we can code the sequence
more compactly as:
Runs of lengths of 0's (or: number of 0's delimited by the 1's):
2,2,1,2,2,0,2,2,1,2,2,0,2,2,1,2,1,0
(apart from the initial term = first differences of the former
characteristic sequences minus 1)

There appears to be some self similarity...
and it seems obvious(?) that this "compactified" version also must be cube
free,
but this is not a sufficient condition for the original to be cube free:
e.g., 2,2,1,2,2,1,... (which is cube-free as such)
corresponds to 001 001 01 001 001 01 which has three "010" towards the end.)

I think the sequence can be constructed in an efficient manner as follows:
(at least I get Robert's values up to 10^4 without any backtracking):

change := false; seq=[0]; word=[0]
while length(seq) < required
.  while  has_cube(concat(seq,word))
.  .    change := true;
.  .    word := increment(word) until not has_cube(word)
.  end while
.  seq := concat( seq, word )
.  if change then word := seq
end while

increment(word ,{ index = length(word) }) := for i from index downto 2 do
.  if word[i] = 0 then return( concat( word[1..i-1], 1))
end do(for); return [1].

Several improvements:
* has_cube(concat(...)) does not need to check everywhere, only with
endpoints of the cube on the second part, and starting point of the cube in
the first part.
* has_cube(word) needs only to check for cubes that end at the end of the
word.
* instead of has_cube I use find_cube which returns the ending point of the
cube found, this is then fed as 2nd arg to increment(...).

- Maximilian



More information about the SeqFan mailing list