|
%I #107 Aug 29 2023 15:12:13
%S 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,
%T 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,
%U 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
%N Lexicographically earliest infinite cubefree word over alphabet {0,1}.
%C Proof that this sequence exists: (Start)
%C 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 which--essentially--makes 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).
%C The subset F of all infinite cubefree binary sequences is nonempty (it contains the Thue-Morse sequence A010060). It admits an infimum (having a lower bound in the whole set) which may or may not be cubefree.
%C 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.
%C 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 - _Jean-Paul Allouche_, May 25 2017
%C 10000 terms were computed using depth-first 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
%C However, at present it is only a conjecture that the terms from 1000 to 10000 are correct. - _N. J. A. Sloane_, May 22 2017
%C 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..k-1],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
%C To prove that the terms of an initial segment W of this sequence computed in this way (which ensures that it is the lex-order 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 Thue-Morse sequence (or any left-truncation of it, also cubefree and overlap-free). 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 overlap-free (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 left-truncations 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(n-1) starting at the second digit of W, etc.) - _M. F. Hasler_, May 21 2017 and May 22 2017
%C 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..L-2],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
%H N. J. A. Sloane, <a href="/A195264/a195264.pdf">Confessions of a Sequence Addict (AofA2017)</a>, slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
%H David W. Wilson, <a href="/A282317/a282317.txt">Table of n, a(n) for n = 0..10000</a> [This is an a-file, not a b-file, since beyond n = 999 these terms are conjectural - _N. J. A. Sloane_, May 22 2017]
%o (PARI) f(n)={a=vector(n);a[1]=-1;p=1;while(p<=n,a[p]+=1;
%o if(a[p]==2,p-=1,valid=1;for(L=1,p\3,e=1;for(j=1,L,
%o if(a[p-j+1]!=a[p-j+1-L]||a[p-j+1]!=a[p-j+1-2*L],e=0;break));
%o if(e,valid=0;break));if(valid,p+=1;if(p>n,return(a));a[p]=-1)));
%o return(a)}
%o v=f(10100);for(i=0,10000,print(i" "v[i+1])) \\ _Robert Gerbicz_, May 01 2017
%o /*** NOTE: To prove that an initial segment of the sequence computed by either of these algorithms (both of which produce the lex-order 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. ***/
%o (PARI) A282317_vec(nMin,v,a=[])={ my( inc(w,n)=forstep(i=n,2,-1, w[i]||return(concat(w[1..i-1],1)));[1], fc(w,n=#w)=for(L=1,n/3,for(k=n-L+1,n,(w[k]!=w[k-L]||w[k]!=w[k-2*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.
%Y For run lengths see A285930.
%Y Other infinite cubefree binary sequences: A010060, A269027.
%Y See also A286940.
%Y For finite binary cubefree strings see A028445.
%K nonn,nice
%O 0
%A _David W. Wilson_, Feb 11 2017
|
