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

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

Offset: 1

Author

Henry Bottomley, Feb 02 2001

Keywords

• nice
• nonn

Comments

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

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

From Vladimir Shevelev, May 23 2017: (Start)

Theorem: The sequence is cubefree.

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

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.

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)

References

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Jeffrey Shallit, Arseny M. Shur, and Stefan Zorcic, New constructions for 3-free and 3+-free binary morphisms, arXiv:2310.15064 [math.CO], 2023. Mentions this sequence.
• Index entries for sequences related to binary expansion of n
• Index entries for characteristic functions

Crossrefs

Characteristic function of A059009.

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

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

Programs

Haskell

a059448 = (`mod` 2) . a023416  -- Reinhard Zumkeller, Mar 01 2012

Maple

s1:=[];
for n from 1 to 200 do
t1:=convert(n,base,2); t2:=subs(1=NULL,t1); s1:=[op(s1),nops(t2) mod 2]; od:
s1;

Mathematica

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

PARI

a(n)=(#binary(n)-hammingweight(n))%2;
vector(99,n,a(n)) /* Joerg Arndt, Sep 11 2020 */

Python

def A059448(n): return (n.bit_length()^n.bit_count())&1 # Chai Wah Wu, Jul 26 2023

Formula

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)|.

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

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

a(n) = A010059(A054429(n)) = (1+A008836(A163511(n)))/2. - Antti Karttunen, May 30 2017

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

Extensions

Name changed by Michel Dekking, Sep 11 2020