A078635 Number of partitions of n into perfect powers.
1, 1, 1, 1, 2, 2, 2, 2, 4, 5, 5, 5, 7, 8, 8, 8, 12, 14, 15, 15, 19, 21, 22, 22, 28, 33, 35, 37, 43, 48, 50, 52, 62, 70, 75, 79, 92, 100, 105, 109, 126, 140, 148, 157, 177, 194, 202, 211, 237, 261, 276, 290, 324, 351, 370, 384, 424, 462, 489, 514, 562, 609, 640, 670, 728
Offset: 0
Keywords
Examples
a(10)=5 since 10 can be written as 9+1, 8+1+1, 4+4+1+1, 4+1+1+1+1+1+1, or 1+1+1+1+1+1+1+1+1+1.
Links
- Michael De Vlieger, Table of n, a(n) for n = 0..10000
Programs
-
Mathematica
t = Union[Flatten[Table[n^k, {n, 1, 60}, {k, 2, 10}]]]; p[n_] := IntegerPartitions[n, All, t]; Table[p[n], {n, 0, 12}] (*shows partitions*) a[n_] := Length@p@n; a /@ Range[0, 80] (* Clark Kimberling, Mar 09 2014 *) With[{nn = 64}, CoefficientList[Series[Product[1/(1 - x^k), {k, Select[Range[nn], # == 1 || GCD @@ FactorInteger[#][[All, -1]] > 1 &]}], {x, 0, nn}], x]] (* Michael De Vlieger, Sep 06 2022 *)
Formula
G.f.: Product_{k=i^j, i>=1, j>=2, excluding duplicates} 1/(1 - x^k). - Ilya Gutkovskiy, Mar 21 2017