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

Author

Ilya Gutkovskiy, Mar 21 2017

Keywords

• nonn

Comments

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

Examples

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

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

Crossrefs

Cf. A001597, A078635, A112344, A112345.

Programs

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]

PARI

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

Formula

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

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