

A086747


BaumSweet 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 BaumSweet 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 0bits 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, evenlength runs of 0bits 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 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 bitwise definition is whether n=0 comprises one 0bit, or no bits at all. A strong argument can be made for a(0)=1 by noting that high 0bits 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 0bits (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, 876890, Dec. 2019. See page 879.


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
JeanPaul 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 593610.
Lukasz Merta, Composition inverses of the variations of the BaumSweet sequence, arXiv:1803.00292 [math.NT], 2018.
Eric Weisstein's World of Mathematics, BaumSweet Sequence
Wikipedia, BaumSweet sequence
J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Contextfree coalgebras, 2013; Journal of Computer and System Sciences, Volume 81, Issue 5, August 2015, Pages 911939.


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)


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



