OFFSET
0,3
COMMENTS
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.
Same parity as the Catalan numbers (A000108). - Paul D. Hanna, Nov 14 2012
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..8191
George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
FORMULA
G.f. satisfies: F(x^2) = (1+F(x))/(x+2). - Ralf Stephan, Jun 28 2003
a(2n) = 2a(n), n>0. a(2n+1) = a(n). - Ralf Stephan, Apr 29 2003
a(n) = sum(k=0, n, C(n+k, k) mod 2). - Benoit Cloitre, Mar 06 2004
a(n) = sum(k=0, n, C(2n-k, n) mod 2). - Paul Barry, Dec 13 2004
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
MATHEMATICA
f[n_] := 2^DigitCount[n, 2, 0]; f[0] = 1; Array[f, 94, 0] (* Robert G. Wilson v *)
PROG
(PARI) a(n)=if(n<1, n==0, (2-n%2)*a(n\2))
(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))
(Haskell)
import Data.List (transpose)
a080100 n = a080100_list !! n
a080100_list = 1 : zs where
zs = 1 : (concat $ transpose [map (* 2) zs, zs])
-- Reinhard Zumkeller, Aug 27 2014, Mar 07 2011
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Reinhard Zumkeller, Jan 28 2003
EXTENSIONS
Keyword base added by Rémy Sigrist, Jan 18 2018
STATUS
approved