login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 12
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

It appears that the positions of 1's are given by sequence A060142. - R. J. Mathar, Apr 19 2013

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

From Kevin Ryde, Jan 23 2020: (Start)

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.

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.

This bit-wise 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.

The bit-wise form (rather than f(x) solution) is often used as the definition of the sequence.  It can be recognised by a state machine, as per Allouche and Shallit.  They include a(0)=1 from Baum and Sweet's series (which Merta, and Winter et al, follow too).

The choice of a(0)=0 or a(0)=1 in a bit-wise 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).

(End)

REFERENCES

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 157.

V. Bergelson et al., A hot shot proof of the generalized Wall theorem, Amer. Math. Monthly, 126:10, 876-890, Dec. 2019. See page 879.

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

Jean-Paul Allouche, Finite Automata and Arithmetic, Séminaire Lotharingien De Combinatoire, volume 30, 1993.

Leonard E. Baum and Melvin M. Sweet, Continued Fractions of Algebraic Power Series in Characteristic 2, Annals of Mathematics, volume 103, number 3, May 1976, pages 593-610.

Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018.

Eric Weisstein's World of Mathematics, Baum-Sweet Sequence

Wikipedia, Baum-Sweet sequence

J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Context-free coalgebras, 2013; Journal of Computer and System Sciences, Volume 81, Issue 5, August 2015, Pages 911-939.

FORMULA

From Kevin Ryde, Jan 23 2020: (Start)

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].

Satisfies g(x) = x*g(x^2) + g(x^4).

a(2n+1) = a(n), for n>=1 (or for all n if a(0)=1).  a(4n) = a(n).  a(4n+2) = 0.

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].

a(n)=1 if A316831(n)=1, a(n)=0 otherwise.

With a(0)=1, pair-wise morphism 00->0000, 01->1001, 10->0100, 11->1101 starting 11.  [Wikipedia "Gandalf61"]

(End)

MAPLE

isNotA086747 := proc(n)

    local csl, b, i ;

    csl := 0 ;

    b := convert(n, base, 2) ;

    for i from 1 to nops(b) do

        if op(i, b) = 1 then

            if type(csl, 'odd') then

                return true ;

            end if;

            csl := 0 ;

        else

            csl := csl+1 ;

        end if;

    end do:

    type(csl, 'odd') ;

end proc:

A086747 := proc(n)

    if isNotA086747(n) then

        0;

    else

        1;

    end if;

end proc: # R. J. Mathar, Apr 19 2013

MATHEMATICA

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 *)

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 *)

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 *)

PROG

(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

(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

CROSSREFS

Cf. A037011, A060142, A316831.

Sequence in context: A188967 A090171 A316832 * A188973 A188970 A244992

Adjacent sequences:  A086744 A086745 A086746 * A086748 A086749 A086750

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Sep 12 2003

EXTENSIONS

More terms from Ray Chandler, Sep 14 2003

a(0) changed to 0 by N. J. A. Sloane, Dec 05 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 09:30 EDT 2020. Contains 334748 sequences. (Running on oeis4.)