VOOZH about

URL: https://oeis.org/A080100

⇱ A080100 - OEIS

login
A080100
a(n) = 2^(number of 0's in binary representation of n).
23
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, 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, 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
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
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) = 2^A080791(n). a(n)=2^A023416(n), n>0.
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
MAPLE
a:= n-> 2^add(1-i, i=Bits[Split](n)):
seq(a(n), n=0..93); # Alois P. Heinz, Aug 18 2025
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
(Python)
def A080100(n): return 1<<n.bit_length()-n.bit_count() # Chai Wah Wu, Aug 18 2025
CROSSREFS
Cf. A001316.
Cf. A002487.
This is Guy Steele's sequence GS(5, 3) (see A135416).
Cf. A048896.
Sequence in context: A109090 A220780 A323915 * A365425 A365381 A161822
KEYWORD
nonn,base
AUTHOR
Reinhard Zumkeller, Jan 28 2003
EXTENSIONS
Keyword base added by Rémy Sigrist, Jan 18 2018
STATUS
approved