login
a(n) = 2^(number of 0's in binary representation of n).
22

%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