login
The parity of the number of zero digits when n is written in binary.
15

%I #78 Oct 24 2023 04:44:49

%S 0,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,

%T 1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,

%U 0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1

%N The parity of the number of zero digits when n is written in binary.

%C Old name was: "If A_k are the terms from 2^(k-1) through to 2^k-1, then A_(k+1) is B_k A_k where B_k is A_k with 0's and 1's swapped, starting from a(1)=0; also parity of number of zero digits when n is written in binary. a(0) not given as it could be 1 or 0 depending on the definition or formula used." - _Michel Dekking_, Sep 11 2020

%C The sequence (when prefixed by 0) is overlap-free [Allouche and Shallit].

%C From _Vladimir Shevelev_, May 23 2017: (Start)

%C Theorem: The sequence is cubefree.

%C Here we show only that the sequence contains no three consecutive equal terms. Indeed, using the recursions below, we have

%C a(4*n)=a(n), a(4*n+1)=1-a(n), a(4*n+2)=1-a(n), a(4*n+3)=a(n), n >= 1, and our statement easily follows. In general, the Theorem could be proved either directly (cf. A269027) or using the remark below from _Jeffrey Shallit_ and the well-known fact [first proved not later than 1912 by Axel Thue (private communication from _Jean-Paul Allouche_)] that the Thue-Morse sequence is cubefree.

%C Note that, by the formulas modulo 4, the sequence is constructed over four terms {a(4*n),a(4*n+1),a(4*n+2),a(4*n+3)} which, starting with a(4), are either {0,1,1,0} or {1,0,0,1}, the first elements of which form {a(n)}. (End)

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 26, Problem 23.

%H Reinhard Zumkeller, <a href="/A059448/b059448.txt">Table of n, a(n) for n = 1..10000</a>

%H Jeffrey Shallit, Arseny M. Shur, and Stefan Zorcic, <a href="https://arxiv.org/abs/2310.15064">New constructions for 3-free and 3+-free binary morphisms</a>, arXiv:2310.15064 [math.CO], 2023. Mentions this sequence.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>

%F a(2n) = 1 - a(n); a(2n+1) = a(n) = 1 - a(2n). If 2^k <= n < 2^(k+1) then a(n) = 1 - a(n-2^(k-1)). a(n) = A023416(n) mod 2 = A059009(n) - 2n = 2n + 1 - A059010(n) = |A010060(n) - A030300(n-1)|.

%F Let b(1)=1 and b(n) = b(n-ceiling(n/2)) - b(n-floor(n/2)); then for n >= 1, a(n) = (1/2)*(1-b(2n+1)). - _Benoit Cloitre_, Apr 26 2005

%F Alternatively, if x is the sequence, then x = 010 mu^2(x), where mu is the Thue-Morse morphism sending 0 to 01 and 1 to 10. - _Jeffrey Shallit_, Jun 06 2016

%F a(n) = A010059(A054429(n)) = (1+A008836(A163511(n)))/2. - _Antti Karttunen_, May 30 2017

%F Alternatively, if x is the sequence, then x = 0 tau(x), where tau is the "twisted" Thue-Morse morphism sending 0 to 10 and 1 to 01. Note that tau^2 = mu^2, giving x = 010 mu^2(x). - _Michel Dekking_, Sep 30 2020

%p s1:=[];

%p for n from 1 to 200 do

%p t1:=convert(n,base,2); t2:=subs(1=NULL,t1); s1:=[op(s1),nops(t2) mod 2]; od:

%p s1;

%t Table[Boole[OddQ[Count[IntegerDigits[n, 2], 0]]], {n, 1, 105}] (* _Jean-François Alcover_, Apr 05 2013 *)

%o (PARI)

%o a(n)=(#binary(n)-hammingweight(n))%2;

%o vector(99,n,a(n)) /* _Joerg Arndt_, Sep 11 2020 */

%o (Haskell)

%o a059448 = (`mod` 2) . a023416 -- _Reinhard Zumkeller_, Mar 01 2012

%o (Python)

%o def A059448(n): return (n.bit_length()^n.bit_count())&1 # _Chai Wah Wu_, Jul 26 2023

%Y Characteristic function of A059009.

%Y Cf. A298952 (complement), A242179 (values +-1).

%Y Cf. A023416 (A080791), A054429, A010059, A010060, A106400.

%K nice,nonn

%O 1,1

%A _Henry Bottomley_, Feb 02 2001

%E Name changed by _Michel Dekking_, Sep 11 2020