%I #76 Oct 11 2023 11:45:25
%S 0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,1,
%T 0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,
%U 0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0
%N Baum-Sweet sequence: a(n) = 1 if binary representation of n contains no block of consecutive zeros of odd length; otherwise a(n) = 0.
%C It appears that the positions of 1's are given by sequence A060142. - _R. J. Mathar_, Apr 19 2013
%C This follows from the definition of the sequence: 4x appends an even number of zeros, while 2x+1 appends a 1. - _Charles R Greathouse IV_, Oct 21 2013
%C From _Kevin Ryde_, Jan 23 2020: (Start)
%C Baum and Sweet consider Laurent series with coefficients mod 2 (GF2[1/x]) and continued fractions developed from such series. One they consider is the unique solution to f(x)^3 + (1/x)*f(x) + 1 = 0, which is f(x) = 1 + 1/x + 0/x^2 + 1/x^3 + ... The coefficients of f are the Baum-Sweet sequence, which is the present sequence except a(0)=1.
%C Baum and Sweet (remark with theorem 2) note that term f_n/x^n has coefficient f_n = 1 if and only if n has only even runs of 0-bits in its binary expansion. They write such f_n just for n>=1, but the constant term 1 in f(x) would be an f_0 = 1.
%C This bitwise form follows from the generating function solution by firstly x instead of 1/x so g(x)^3 + x*g(x) + 1 = 0, then f(x)^2=f(x^2) which is true of any series with coefficients mod 2, then multiply through by g(x) so g(x) = x*g(x^2) + g(x^4). x*g(x^2) copies a(n) to odd terms a(2n+1) (so its own odd bisection). g(x^4) copies a(n) to a(4n) similarly. Nothing is copied to 4n+2 so those terms are 0. These are the recurrence below. Repeatedly applied, even-length runs of 0-bits are skipped until reaching final a(0)=1.
%C The bitwise form (rather than f(x) solution) is often used as the definition of the sequence. It can be recognized by a state machine, per Allouche and Shallit. They include a(0)=1 from Baum and Sweet's series (which Merta, and Winter et al., follow too).
%C The choice of a(0)=0 or a(0)=1 in a bitwise definition is whether n=0 comprises one 0-bit, or no bits at all. A strong argument can be made for a(0)=1 by noting that high 0-bits are not considered when testing runs of 0s in an n>=1, and ignoring all high 0s in n=0 leaves an empty bit string, which is no odd run of 0s. Allouche and Shallit's state A skips optional leading 0s explicitly. Their output value 1 there gives a(0)=1 for n=0 as any number of 0-bits (none, one, more).
%C (End)
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 157.
%H N. J. A. Sloane, <a href="/A086747/b086747.txt">Table of n, a(n) for n = 0..10000</a>
%H Jean-Paul Allouche, <a href="http://www.emis.de/journals/SLC/opapers/s30allouche.html">Finite Automata and Arithmetic</a>, Séminaire Lotharingien De Combinatoire, volume 30, 1993.
%H Leonard E. Baum and Melvin M. Sweet, <a href="http://www.jstor.org/stable/1970953">Continued Fractions of Algebraic Power Series in Characteristic 2</a>, Annals of Mathematics, volume 103, number 3, May 1976, pages 593-610.
%H Vitaly Bergelson and Joseph Vandehey, <a href="https://www.jstor.org/stable/48661409">A hot spot proof of the generalized Wall theorem</a>, Amer. Math. Monthly, 126:10, 876-890, Dec. 2019. See page 879.
%H Lukasz Merta, <a href="https://arxiv.org/abs/1803.00292">Composition inverses of the variations of the Baum-Sweet sequence</a>, arXiv:1803.00292 [math.NT], 2018.
%H Joris Nieuwveld, <a href="https://arxiv.org/abs/2108.11382">Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding</a>, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.
%H Narad Rampersad and Max Wiebe, <a href="https://arxiv.org/abs/2309.04012">Sums of products of binomial coefficients mod 2 and 2-regular sequences</a>, arXiv:2309.04012 [math.NT], 2023.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Baum-SweetSequence.html">Baum-Sweet Sequence</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Baum-Sweet_sequence">Baum-Sweet sequence</a>
%H J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, <a href="https://web.archive.org/web/20160319213413/http://oai.cwi.nl/oai/asset/21313/21313A.pdf">Context-free coalgebras</a>, 2013; Journal of Computer and System Sciences, Volume 81, Issue 5, August 2015, Pages 911-939.
%F From _Kevin Ryde_, Jan 23 2020: (Start)
%F Let g(x) = 1 + Sum_{n>=1} a(n)*x^n. Satisfies g(x)^3 + x*g(x) + 1 = 0 with coefficients mod 2 [Baum and Sweet].
%F Satisfies g(x) = x*g(x^2) + g(x^4).
%F a(2n+1) = a(n), for n>=1 (or for all n if a(0)=1). a(4n) = a(n). a(4n+2) = 0.
%F Morphism A->AB, B->CB, C->BD, D->DD starting A and final mapping A->a(0), B->1, C->0, D->0 [Allouche, section 2.4 example 4].
%F a(n)=1 if A316831(n)=1, a(n)=0 otherwise.
%F With a(0)=1, pairwise morphism 00->0000, 01->1001, 10->0100, 11->1101 starting 11. [Wikipedia "Gandalf61"]
%F (End)
%p isNotA086747 := proc(n)
%p local csl,b,i ;
%p csl := 0 ;
%p b := convert(n,base,2) ;
%p for i from 1 to nops(b) do
%p if op(i,b) = 1 then
%p if type(csl,'odd') then
%p return true ;
%p end if;
%p csl := 0 ;
%p else
%p csl := csl+1 ;
%p end if;
%p end do:
%p type(csl,'odd') ;
%p end proc:
%p A086747 := proc(n)
%p if isNotA086747(n) then
%p 0;
%p else
%p 1;
%p end if;
%p end proc: # _R. J. Mathar_, Apr 19 2013
%t a[n_] := Block[{b = Plus @@ Union@ Mod[ Length@# & /@ Select[ Union@ Split@ IntegerDigits[n, 2], MemberQ[ #, 0] &], 2]}, If[b == 0, 1, 0]]; a[0] = 1; Table[a@n, {n, 0, 104}] (* _Robert G. Wilson v_, May 03 2010 *)
%t a[0] = 1; a[1] = 1; a[n_] := a[n] = Block[{k = n}, While[ Mod[k, 4] == 0, k /= 4]; If[ OddQ@k, a[(k - 1)/2], 0]]; Table[a@n, {n, 0, 104}] (* _Robert G. Wilson v_, May 03 2010 *)
%t Nest[Partition[ Flatten[ # /. {{0, 0} -> {0, 0, 0, 0}, {0, 1} -> {1, 0, 0, 1}, {1, 0} -> {0, 1, 0, 0}, {1, 1} -> {1, 1, 0, 1}}], 2] &, {1, 1}, 6] // Flatten (* _Robert G. Wilson v_, May 03 2010 *)
%o (PARI) a(n)=if(n<3,n<2,if(n%2,a(n\2),n%4==0&&a(n/4))) \\ _Charles R Greathouse IV_, Oct 21 2013
%o (PARI) a(n) = if(n==0,0, my(z=0); for(i=0,logint(n,2), if(bittest(n,i), if(z%2,return(0));z=0, z++)); 1); \\ _Kevin Ryde_, Jan 23 2020
%o (Python)
%o from itertools import groupby
%o def a(n): return int(all(len(list(g))%2 == 0 or k == '1' for k, g in groupby(bin(n)[2:])))
%o print([a(n) for n in range(105)]) # _Michael S. Branicky_, Aug 27 2021
%Y Cf. A037011, A060142, A316831.
%K nonn,easy
%O 0,1
%A _N. J. A. Sloane_, Sep 12 2003
%E More terms from _Ray Chandler_, Sep 14 2003
%E a(0) changed to 0 by _N. J. A. Sloane_, Dec 05 2019