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

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

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

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

Prog

(PARI)
a(n)=(#binary(n)-hammingweight(n))%2;
vector(99, n, a(n)) /* Joerg Arndt, Sep 11 2020 */
(Haskell)
a059448 = (`mod` 2) . a023416  -- Reinhard Zumkeller, Mar 01 2012
(Python)
def A059448(n): return (n.bit_length()^n.bit_count())&1 # Chai Wah Wu, Jul 26 2023

Crossrefs

Characteristic function of A059009.

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

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

Sequence in context: A082401 A157238 A337546 * A283318 A288633 A284775

Adjacent sequences: A059445 A059446 A059447 * A059449 A059450 A059451

Keyword

nice,nonn

Author

Henry Bottomley, Feb 02 2001

Extensions

Name changed by Michel Dekking, Sep 11 2020

Status

approved