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.

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

Offset: 0

Author

N. J. A. Sloane, Sep 12 2003

Keywords

• nonn
• easy

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

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

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

(End)

References

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

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.
• Vitaly Bergelson and Joseph Vandehey, A hot spot proof of the generalized Wall theorem, Amer. Math. Monthly, 126:10, 876-890, Dec. 2019. See page 879.
• Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018.
• Joris Nieuwveld, Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.
• Narad Rampersad and Max Wiebe, Sums of products of binomial coefficients mod 2 and 2-regular sequences, arXiv:2309.04012 [math.NT], 2023.
• 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.

Crossrefs

Cf. A037011, A060142, A316831.

Programs

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

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

Python

from itertools import groupby
def a(n): return int(all(len(list(g))%2 == 0 or k == '1' for k, g in groupby(bin(n)[2:])))
print([a(n) for n in range(105)]) # Michael S. Branicky, Aug 27 2021

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, pairwise morphism 00->0000, 01->1001, 10->0100, 11->1101 starting 11. [Wikipedia "Gandalf61"]

(End)

Extensions

More terms from Ray Chandler, Sep 14 2003

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