|
| |
|
|
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
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
|
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
|
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:
if isNotA086747(n) then
0;
else
1;
end if;
|
|
|
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==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:])))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
