# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a086747
Showing 1-1 of 1

%I A086747 #76 Oct 11 2023 11:45:25
%S A086747 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 A086747 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 A086747 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 A086747 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 A086747 It appears that the positions of 1's are given by sequence A060142. - _R. J. Mathar_, Apr 19 2013
%C A086747 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 A086747 From _Kevin Ryde_, Jan 23 2020: (Start)
%C A086747 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 A086747 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 A086747 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 A086747 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 A086747 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 A086747 (End)
%D A086747 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 157.
%H A086747 N. J. A. Sloane, <a href="/A086747/b086747.txt">Table of n, a(n) for n = 0..10000</a>
%H A086747 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 A086747 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 A086747 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 A086747 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 A086747 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 A086747 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 A086747 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Baum-SweetSequence.html">Baum-Sweet Sequence</a>
%H A086747 Wikipedia, <a href="http://en.wikipedia.org/wiki/Baum-Sweet_sequence">Baum-Sweet sequence</a>
%H A086747 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 A086747 From _Kevin Ryde_, Jan 23 2020: (Start)
%F A086747 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 A086747 Satisfies g(x) = x*g(x^2) + g(x^4).
%F A086747 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 A086747 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 A086747 a(n)=1 if A316831(n)=1, a(n)=0 otherwise.
%F A086747 With a(0)=1, pairwise morphism 00->0000, 01->1001, 10->0100, 11->1101 starting 11.  [Wikipedia "Gandalf61"]
%F A086747 (End)
%p A086747 isNotA086747 := proc(n)
%p A086747     local csl,b,i ;
%p A086747     csl := 0 ;
%p A086747     b := convert(n,base,2) ;
%p A086747     for i from 1 to nops(b) do
%p A086747         if op(i,b) = 1 then
%p A086747             if type(csl,'odd') then
%p A086747                 return true ;
%p A086747             end if;
%p A086747             csl := 0 ;
%p A086747         else
%p A086747             csl := csl+1 ;
%p A086747         end if;
%p A086747     end do:
%p A086747     type(csl,'odd') ;
%p A086747 end proc:
%p A086747 A086747 := proc(n)
%p A086747     if isNotA086747(n) then
%p A086747         0;
%p A086747     else
%p A086747         1;
%p A086747     end if;
%p A086747 end proc: # _R. J. Mathar_, Apr 19 2013
%t A086747 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 A086747 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 A086747 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 A086747 (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 A086747 (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 A086747 (Python)
%o A086747 from itertools import groupby
%o A086747 def a(n): return int(all(len(list(g))%2 == 0 or k == '1' for k, g in groupby(bin(n)[2:])))
%o A086747 print([a(n) for n in range(105)]) # _Michael S. Branicky_, Aug 27 2021
%Y A086747 Cf. A037011, A060142, A316831.
%K A086747 nonn,easy
%O A086747 0,1
%A A086747 _N. J. A. Sloane_, Sep 12 2003
%E A086747 More terms from _Ray Chandler_, Sep 14 2003
%E A086747 a(0) changed to 0 by _N. J. A. Sloane_, Dec 05 2019

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE