A073119 Total number of parts which are positive powers of 2 in all partitions of n.

0, 1, 1, 4, 5, 10, 14, 26, 35, 56, 77, 116, 157, 226, 302, 424, 560, 762, 998, 1334, 1727, 2270, 2914, 3779, 4809, 6163, 7781, 9875, 12378, 15565, 19383, 24191, 29934, 37093, 45643, 56201, 68789, 84212, 102564, 124903, 151424, 183499, 221508

Offset

1,4

Links

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 1..10000 (terms 1..2000 from Alois P. Heinz)

Formula

a(n) = Sum_{k=1..n} A007814(k)*A000041(n-k).

G.f.: g(x) = (Sum_{i>0} x^(h(i))/(1-x^(h(i))))/Product_{i>0}(1 - x^i), where h(i) = 2^i. - Emeric Deutsch, Sep 19 2016.

Conjecture: a(n) ~ exp(sqrt(2*n/3)*Pi)/(2*Pi*sqrt(2*n)) ~ p(n) * sqrt(6*n)/Pi, where p(n) is the partition function A000041. - Vaclav Kotesovec, Oct 07 2016

Example

a(5) = 5 because in the partitions [1,1,1,1,1], [1,1,1,2'], [1,2'2'], [1,1,3], [2',3],[1,4'], [5] we have 5 positive powers of 2 (they are marked). - Emeric Deutsch, Sep 19 2016.

Maple

p2:= proc(n) p2(n):= is(n=2^ilog2(n)) end: p2(1):= false:
b:= proc(n, i) option remember; local t, l;
      if n<0 then [0, 0]
    elif n=0 then [1, 0]
    elif i<1 then [0, 0]
    else t:= b(n, i-1);
         l:= b(n-i, i);
         [t[1]+l[1], t[2]+l[2]+ `if`(p2(i), l[1], 0)]
      fi
    end:
a:= n-> b(n, n)[2]:
seq(a(n), n=1..50);  # Alois P. Heinz, Sep 29 2011

Mathematica

Needs["DiscreteMath`Combinatorica`"]; f[n_] := Length[ Select[ Log[2, Flatten[ Partitions[n]]], IntegerQ[ # ] && # > 0 & ]]; Table[ f[n], {n, 1, 45}]
a[n_] := Sum[IntegerExponent[k, 2]*PartitionsP[n-k], {k, 1, n}]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Jan 28 2014 *)

Crossrefs

Cf. A024786, A000070.

Sequence in context: A322610 A322468 A116930 * A002257 A101528 A119040

Adjacent sequences: A073116 A073117 A073118 * A073120 A073121 A073122

Keyword

easy,nonn

Author

Vladeta Jovovic, Aug 24 2002

Extensions

Edited and extended by Robert G. Wilson v, Aug 26 2002

Status

approved