

A282317


Lexicographically earliest infinite cubefree word over alphabet {0,1}.


8



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, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 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, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 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, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0


COMMENTS

Proof that this sequence exists: (Start)
Consider the set of all infinite binary sequences equipped with the usual topology (two sequences are "close" if they coincide on a long prefix). This is a metrizable topology whichessentiallymakes this set "equal" to the real numbers in [0,1) ("essentially" because of the ambiguity caused by the fact that positive rational numbers k/2^m have two representations, ending with all 0's or all 1's).
The subset F of all infinite cubefree binary sequences is nonempty (it contains the ThueMorse sequence A010060). It admits an infimum (having a lower bound in the whole set) which may or may not be cubefree.
To prove that this infimum is cubefree, it would be enough to prove that the set F is (topologically) closed. Alternatively, that its complement G, the set of sequences containing at least one cube, is an open set.
Take a binary sequence S containing a cube. Take a prefix of S that is long enough to contain this cube. All sequences with this prefix contain a cube and are close to S, and provide an open interval of noncubefree sequences centered at S. So G is an open set. QED  JeanPaul Allouche, May 25 2017
10000 terms were computed using depthfirst search with backtracking with 200 guard elements. The observed backtracking depths were small, strongly suggesting that all 10000 terms are correct.  David W. Wilson, Feb 11 2017
However, at present it is only a conjecture that the terms from 1000 to 10000 are correct.  N. J. A. Sloane, May 22 2017
I reproduced these 10000 terms with an algorithm that did not need any backtracking in the strict sense (cf. PARI code), as follows: (1) Start with S := 0. (2) Let W := S. (3) While SW is not cubefree, "increment" W (see below for details) at the point where the first cube in SW ends. (4) Let S := SW and goto (2). By "increment W at the point k" we mean: if W[k]=1 then decrease k until W[k]=0; now set W[k]=1 and delete all further digits (i.e., W := concat(W[1..k1],1)). If this never results in a maximal cubefree word S (cf. A282133), then the algorithm yields the correct sequence (minimal and cubefree by construction and infinite by hypothesis).  M. F. Hasler, May 20 2017
To prove that the terms of an initial segment W of this sequence computed in this way (which ensures that it is the lexorder earliest cubefree sequence of that length) are correct, it is sufficient to show that W can be extended to an infinite cubefree sequence. This is the case if WT is cubefree, where T = A010060 is the ThueMorse sequence (or any lefttruncation of it, also cubefree and overlapfree). Following an idea of N. J. A. Sloane, we show that it is sufficient to check that WT' is cubefree, where T' is T truncated to twice the length of W. (This is indeed the case for the first 999 terms.) Indeed, if WT = XXX... with length(X) > length(W), let X = WY, then WT = WYWYWY... so T = YWYWY... = ABABA... with YW =: AB, length(A) = 1, which is impossible since T is known to be overlapfree (see A010060). Thus, if WT starts with a cube XXX, then length(X) <= length(W). To cover the case where the cube XXX would start later in WT, repeat the reasoning for all lefttruncations of W. This completes the proof. (If length(W) = n, we need only to check for cubes of length <= 3n starting at the beginning, of length <= 3(n1) starting at the second digit of W, etc.)  M. F. Hasler, May 21 2017 and May 22 2017
See A286940 for the lengths of the words W successively appended by this algorithm. These lengths L are sufficient to reconstruct the words W = concat(S[0..L2],1) (except for the first two 1's which correspond to W = 0). There we give a pattern for that sequence of lengths conjectured to be valid for about 65*3^8 terms, corresponding to more than 10^7 terms of A282317. Beyond that point the behavior is unclear.  M. F. Hasler, May 21 2017


LINKS

Table of n, a(n) for n=0..129.
N. J. A. Sloane, Confessions of a Sequence Addict (AofA2017), slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
David W. Wilson, Table of n, a(n) for n = 0..10000 [This is an afile, not a bfile, since beyond n = 999 these terms are conjectural  N. J. A. Sloane, May 22 2017]


PROG

(PARI) f(n)={a=vector(n); a[1]=1; p=1; while(p<=n, a[p]+=1;
if(a[p]==2, p=1, valid=1; for(L=1, p\3, e=1; for(j=1, L,
if(a[pj+1]!=a[pj+1L]a[pj+1]!=a[pj+12*L], e=0; break));
if(e, valid=0; break)); if(valid, p+=1; if(p>n, return(a)); a[p]=1)));
return(a)}
v=f(10100); for(i=0, 10000, print(i" "v[i+1])) \\ Robert Gerbicz, May 01 2017
/*** NOTE: To prove that an initial segment of the sequence computed by either of these algorithms (both of which produce the lexorder first cubefree sequence of that length) is correct, it is sufficient to show that its concatenation with a segment of A010060 of twice its length is cubefree, cf. comments. E.g., in case the computed terms end in ..., 0, 0, one would start with the second or some other nonzero term of A010060. ***/
(PARI) A282317_vec(nMin, v, a=[])={ my( inc(w, n)=forstep(i=n, 2, 1, w[i]return(concat(w[1..i1], 1))); [1], fc(w, n=#w)=for(L=1, n/3, for(k=nL+1, n, (w[k]!=w[kL]w[k]!=w[k2*L])&& next(2)); return(n)), fcc(x, y, z=concat(x, y), t)=for(n=#x+1, #z, (t=fc(z, n))&&return(t#x)), w=if(a, a, [0]), c, p); while(#a<nMin, c=0; while( p=fcc(a, w), !c&&c++&&bittest(v, 1)&&printf("/*new w*/"); until( !p=fc(w), w=inc(w, p)); bittest(v, 2)&&#w<2&&printf("Reached w=%d at #a=%d. ", w, #a)); a=concat(a, w); bittest(v, 4)&&print1(#w", "); bittest(v, 0)&&print1(w", "); c&&w=a); a} \\ The 2nd optional argument allows one to display additional information. The until() loop gives only 2.5% speedup. M. F. Hasler, May 02 2017. The capability of restarting the computation with a given initial sequence (the 3rd optional argument) added May 19 2017.


CROSSREFS

For run lengths see A285930.
Other infinite cubefree binary sequences: A010060, A269027, A285196.
See also A286940.
For finite binary cubefree strings see A028445.
Sequence in context: A189628 A289239 A188432 * A212126 A144605 A154103
Adjacent sequences: A282314 A282315 A282316 * A282318 A282319 A282320


KEYWORD

nonn


AUTHOR

David W. Wilson, Feb 11 2017


STATUS

approved



