A064572 Number of ways to partition n into parts which are all powers of some integer k.

0, 1, 2, 5, 6, 10, 11, 17, 20, 26, 27, 38, 39, 47, 51, 65, 66, 82, 83, 102, 107, 123, 124, 153, 156, 178, 185, 216, 217, 254, 255, 297, 304, 342, 346, 408, 409, 457, 466, 535, 536, 609, 610, 690, 704, 780, 781, 895, 898, 998, 1009, 1130, 1131, 1263, 1268, 1418

Offset: 1

Author

Marc LeBrun, Sep 20 2001

Keywords

• easy
• nonn

Comments

Number of ways to partition n as Sum_i k^e_i, where the exponents e_i are not all 0.

The exponents cannot all be 0, e.g. a(2)=1 arises from 2^1, and does not include 2^0+2^0. - Shujing Lyu, Apr 23 2016

Examples

			a(4)=5: 4^1, 3^1+3^0, 2^2, 2*2^1, 2^1+2*2^0.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000 (terms 1..220 from Shujing Lyu)

Crossrefs

Cf. A028422, A064573, A064574, A064575, A064576, A064577, A292477.

Programs

PARI

first(n)={Vec(sum(k=2, n, 1/prod(r=0, logint(n,k), 1-x^(k^r) + O(x*x^n)) - 1/(1-x), 0), -n)} \\ Andrew Howroyd, Dec 29 2017

Formula

G.f.: Sum_{k>=2} 1/(Product_{r>=0} 1-x^(k^r)) - 1/(1-x). - Andrew Howroyd, Dec 29 2017