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.
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
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
KEYWORD
nice,nonn
AUTHOR
Henry Bottomley, Feb 02 2001
EXTENSIONS
Name changed by Michel Dekking, Sep 11 2020
STATUS
approved