A073267 Number of compositions (ordered partitions) of n into exactly two powers of 2.
0, 0, 1, 2, 1, 2, 2, 0, 1, 2, 2, 0, 2, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0
Offset: 0
Keywords
Examples
For 2 there is only composition {1+1}, for 3 there is {1+2, 2+1}, for 4 {2+2}, for 5 {1+4, 4+1}, for 6 {2+4,4+2}, for 7 none, thus a(2)=1, a(3)=2, a(4)=1, a(5)=2, a(6)=2 and a(7)=0.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
- Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, Catalan and Motzkin numbers modulo 4 and 8, Eur. J. Combinat. 29 (2008) 1449-1466.
Crossrefs
The second row of the table A073265. The essentially same sequence 1, 1, 2, 1, 2, 2, 0, 1, ... occurs for first time in A073202 as row 105 (the fix count sequence of A073290). The positions of 1's for n > 1 is given by the characteristic function of A000079, i.e. A036987 with offset 1 instead of 0 and the positions of 2's is given by A018900. Cf. also A023359.
Cf. A036987. [Gary W. Adamson, Feb 23 2010]
Programs
-
Haskell
a073267 n = sum $ zipWith (*) a209229_list $ reverse $ take n a036987_list -- Reinhard Zumkeller, Mar 07 2012
-
Maple
f:= proc(n) local d; d:= convert(convert(n,base,2),`+`); if d=2 then 2 elif d=1 then 1 else 0 fi end proc: 0, 0, seq(f(n),n=2..100); # Robert Israel, Jul 07 2016
-
Mathematica
Table[Count[Map[{#, n - #} &, Range[0, n]], k_ /; Times @@ Boole@ Map[IntegerQ@ Log2@ # &, k] == 1], {n, 0, 88}] (* Michael De Vlieger, Jul 08 2016 *) -
PARI
N=166; x='x+O('x^N); v=Vec( 'a0 + sum(k=0,ceil(log(N)/log(2)), x^(2^k) )^2 ); v[1] -= 'a0; v /* Joerg Arndt, Oct 21 2012 */ -
Python
def A073267(n): return m if n>1 and (m:=n.bit_count())<3 else 0 # Chai Wah Wu, Oct 30 2024
Formula
G.f.: (Sum_{k>=0} x^(2^k) )^2. - Vladeta Jovovic, Mar 28 2005
a(n+1) = A000108(n) mod 4, n>=1 [Theorem 2.3 of Eu et al.]. - R. J. Mathar, Feb 27 2008
a(n) = sum (A209229(k)*A036987(n-k): k = 0..n), convolution of characteristic functions of 2^n and 2^n-1. [Reinhard Zumkeller, Mar 07 2012]
a(n+2) = A000168(n) mod 4. - John M. Campbell, Jul 07 2016
Comments