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