A284171 Number of partitions of n into distinct perfect powers (including 1).

1, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 3, 2, 1, 2, 3, 2, 1, 2, 3, 3, 2, 4, 5, 3, 2, 4, 5, 3, 2, 4, 6, 4, 2, 4, 7, 5, 2, 5, 8, 5, 2, 5, 8, 6, 3, 5, 10, 8, 4, 6, 10, 8, 4, 6, 10, 9, 5, 7, 11, 10, 6, 8, 12, 10, 6, 8, 13, 11, 7, 9, 15, 13, 7, 10, 16, 14, 8, 10, 16, 15, 9, 10, 17, 16, 9, 11

Offset

0,10

Comments

Differs from the sequence A112345 which does not consider 1 as a perfect power.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Perfect Power

Index entries for related partition-counting sequences

Formula

G.f.: Product_{k>=1} (1 + x^A001597(k)).

a(n) = A112345(n-1) + A112345(n).

Example

a(25) = 3 because we have [25], [16, 9] and [16, 8, 1].

Mathematica

nmax = 100; CoefficientList[Series[(1 + x) Product[(1 + Boole[GCD @@ FactorInteger[k][[All, 2]] > 1] x^k), {k, 1, nmax}], {x, 0, nmax}], x]

Prog

(PARI) Vec((1 + x) * prod(k=1, 100, 1 + (gcd(factorint(k)[, 2])>1)*x^k) + O(x^101)) \\ Indranil Ghosh, Mar 21 2017

Crossrefs

Cf. A001597, A078635, A112344, A112345.

Sequence in context: A334540 A334462 A054848 * A286320 A330888 A194525

Adjacent sequences: A284168 A284169 A284170 * A284172 A284173 A284174

Keyword

nonn

Author

Ilya Gutkovskiy, Mar 21 2017

Status

approved