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,3

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

Links

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

Formula

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

Example

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

Prog

(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

Crossrefs

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

Sequence in context: A077471 A273324 A238096 * A032399 A276496 A007969

Adjacent sequences: A064569 A064570 A064571 * A064573 A064574 A064575

Keyword

easy,nonn

Author

Marc LeBrun, Sep 20 2001

Status

approved