|
%I #33 Aug 29 2023 03:26:23
%S 0,1,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,0,1,1,0,0,1,1,0,
%T 1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,0,1,1,0,0,1,
%U 1,0,1,0,0,1,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1
%N Define a sequence of binary words by w(1) = 01 and w(n+1) = w(n)w(n)Reverse[w(n)]. Sequence gives the limiting word w(infinity).
%C This is a cube-free sequence [Allouche and Shallit]. - _N. J. A. Sloane_, Aug 29 2023
%C The article by W. Hebisch and M. Rubey gives a conjectured functional equation for the g.f. for this sequence. - _N. J. A. Sloane_, Sep 08 2010
%C The formula in Hebisch and Rubey has an extra left parenthesis before f(x). - _Michael Somos_, Jan 03 2011
%C From _Michel Dekking_, Sep 10 2020: (Start)
%C This sequence is an automatic sequence, i.e., the letter-to-letter image of the fixed point of a uniform morphism mu.
%C In fact, one can take the alphabet {1,2,3,4} with the morphism
%C mu: 1->121, 2->234, 3->123, 4->434,
%C and the letter-to-letter map g defined by
%C g: 1->0, 2->1, 3->1, 4->0.
%C Then (a(n)) = g(x), where x = 121234121... is the fixed point of the morphism mu starting with 1.
%C This is obtained by translating the recursion relation for w to the morphism a->aab, b->abb, and then decorating the fixed point aabaababb.... of this morphism with a->01, b->10, since the recursion starts at w(1) = 01.
%C It is well-known that decorated fixed points of morphisms are morphic sequences, and the 'natural' algorithm to achieve this (see my paper "Morphic words, Beatty sequences and integer images of the Fibonacci language") yields a morphism on an alphabet of 2+2 = 4 symbols. In general there are several choices for mu. Here we have chosen mu such that it has constant length, i.e., the morphism is uniform.
%C (End)
%C Morphism a->aab, b->abb is Stewart's choral sequence A116178 (ternary lowest non-1 digit, halved). Decoration 01 and 10 is then an interleaving of that sequence and its complement so a(2n+1) = A116178(n) and a(2n+2) = 1-A116178(n) = A136442(n). - _Kevin Ryde_, Sep 29 2020
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 28, #49.
%H M. Dekking, <a href="https://doi.org/10.1016/j.tcs.2019.12.036">Morphic words, Beatty sequences and integer images of the Fibonacci language</a>, Theoretical Computer Science 809, 407-417 (2020).
%H W. Hebisch and M. Rubey, <a href="http://arxiv.org/abs/math/0702086">Extended Rate, more GFUN</a>, arXiv:math/0702086 [math.CO], 2007-2010.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ReverendBacksAbbeyFloor.html">Reverend Back's Abbey Floor</a>
%F G.f. f(x) satisfies: (1+x+x^2) * f(x) - x^2 * f(x^3) = x * (1-x^4)^2 / ((1-x) * (1-x^2) * (1-x^6)) = A096285(x)/x^2. - _Michael Somos_, Jan 03 2011
%e 01, 010110, 010110010110011010, ...
%p with(ListTools);
%p f:=proc(S) global f2;
%p [op(S), op(S), op(Reverse(S))]; end;
%p S:=[0, 1];
%p for n from 1 to 6 do S:=f(S): od:
%p S; # _N. J. A. Sloane_, Aug 29 2023
%t m = maxExponent = 105;
%t f[_] = 0;
%t Do[f[x_] = (x^2 f[x^3] + ((1-x^4)^2 x)/((1-x)(1-x^2)(1-x^6)))/(1+x+x^2) + O[x]^m // Normal, {m}];
%t CoefficientList[f[x], x] (* _Jean-François Alcover_, Aug 17 2018, after _Michael Somos_ *)
%o (PARI) a(n) = my(b=n%2,d); n=(n-1)>>1; while([n,d]=divrem(n,3);d==1,); d==2*b; \\ _Kevin Ryde_, Sep 29 2020
%Y Cf. A116178 (odd bisection), A136442 (even bisection).
%Y The Thue-Morse sequence A010060 is a classical example of a cubefree sequence.
%Y A282317 is the lexicographically earliest binary cubefree sequence.
%Y Cf. also A064990, A285196.
%K nonn
%O 1,1
%A _Eric W. Weisstein_, Apr 09 2006
%E Edited by _N. J. A. Sloane_, Feb 13 2008
|
