%I #37 Jun 24 2021 01:46:38
%S 1,1,2,1,4,2,2,1,8,4,4,2,4,2,2,1,16,8,8,4,8,4,4,2,8,4,4,2,4,2,2,1,32,
%T 16,16,8,16,8,8,4,16,8,8,4,8,4,4,2,16,8,8,4,8,4,4,2,8,4,4,2,4,2,2,1,
%U 64,32,32,16,32,16,16,8,32,16,16,8,16,8,8,4,32,16,16,8,16,8,8,4,16,8,8,4,8,4
%N a(n) = 2^(number of 0's in binary representation of n).
%C Number of numbers k, 0<=k<=n, such that (k AND n) = 0 (bitwise logical AND): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080099.
%C Same parity as the Catalan numbers (A000108). - _Paul D. Hanna_, Nov 14 2012
%H Reinhard Zumkeller, <a href="/A080100/b080100.txt">Table of n, a(n) for n = 0..8191</a>
%H George Beck and Karl Dilcher, <a href="https://arxiv.org/abs/2106.10400">A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence</a>, arXiv:2106.10400 [math.CO], 2021.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%F G.f. satisfies: F(x^2) = (1+F(x))/(x+2). - _Ralf Stephan_, Jun 28 2003
%F a(2n) = 2a(n), n>0. a(2n+1) = a(n). - _Ralf Stephan_, Apr 29 2003
%F a(n) = 2^A080791(n). a(n)=2^A023416(n), n>0.
%F a(n) = sum(k=0, n, C(n+k, k) mod 2). - _Benoit Cloitre_, Mar 06 2004
%F a(n) = sum(k=0, n, C(2n-k, n) mod 2). - _Paul Barry_, Dec 13 2004
%F G.f. satisfies: A(x) = Sum_{n>=0} [A(x)^n (mod 2)]*x^n, where A(x)^n (mod 2) reduces all coefficients modulo 2 to {0,1}. - _Paul D. Hanna_, Nov 14 2012
%t f[n_] := 2^DigitCount[n, 2, 0]; f[0] = 1; Array[f, 94, 0] (* _Robert G. Wilson v_ *)
%o (PARI) a(n)=if(n<1,n==0,(2-n%2)*a(n\2))
%o (PARI) a(n)=local(A,m); if(n<0,0,m=1; A=1+O(x); while(m<=n,m*=2; A=subst(A,x,x^2)*(2+x)-1); polcoeff(A,n))
%o (Haskell)
%o import Data.List (transpose)
%o a080100 n = a080100_list !! n
%o a080100_list = 1 : zs where
%o zs = 1 : (concat $ transpose [map (* 2) zs, zs])
%o -- _Reinhard Zumkeller_, Aug 27 2014, Mar 07 2011
%Y Cf. A001316.
%Y Cf. A002487.
%Y This is Guy Steele's sequence GS(5, 3) (see A135416).
%Y Cf. A048896.
%Y Cf. A023416, A080791.
%K nonn,base
%O 0,3
%A _Reinhard Zumkeller_, Jan 28 2003
%E Keyword base added by _Rémy Sigrist_, Jan 18 2018