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