A112344 Number of partitions of n into perfect powers.

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 4, 2, 1, 0, 4, 2, 1, 0, 6, 5, 2, 2, 6, 5, 2, 2, 10, 8, 5, 4, 13, 8, 5, 4, 17, 14, 8, 9, 20, 17, 8, 9, 26, 24, 15, 14, 34, 27, 19, 14, 40, 38, 27, 25, 48, 47, 31, 30, 58, 59, 44, 42, 75, 68, 55, 47, 91, 86, 70, 67, 110, 106, 81, 81, 130, 134, 104

Offset

1,8

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Perfect Power

Eric Weisstein's World of Mathematics, Partition

Example

a(20) = #{16+4, 8+8+4, 8+4+4+4, 4+4+4+4+4} = 4.

Maple

N:= 200: # to get a(1) to a(N)
Pows:= {seq(seq(k^p, p=2..floor(log[k](N))), k=2..floor(sqrt(N)))}:
g:= proc(n, q) option remember; if n = 0 then 1 else `+`(seq(procname(n-r, r), r=select(`<=`, Pows, min(q, n)))) fi end proc:
seq(g(n, n), n=1..N); # Robert Israel, Nov 04 2015

Mathematica

M = 200; (* to get a(1) to a(M) *)
Pows = Table[k^p, {k, 2, Floor[Sqrt[M]]}, {p, 2, Floor[Log[k, M]]}] // Flatten // Union;
g[n_, q_] := g[n, q] = If[n == 0, 1, Plus @@ Table[g[n - r, r], {r, Select[Pows, # <= Min[q, n]&]}]];
Table[g[n, n], {n, 1, M}] (* Jean-François Alcover, Feb 03 2018, translated from Robert Israel's Maple code *)

Prog

(PARI) leastp(n) = {while(!ispower(n), n--; if (n==0, return (0))); n; }
a(n) = {pmax = leastp(n); if (! pmax, return (0)); nb = 0; forpart(p=n, nb += (#select(x->ispower(x), Vec(p)) == #p), [4, pmax]); nb; } \\ Michel Marcus, Nov 04 2015

Crossrefs

Cf. A001597, A000041, A001156, A078134, A062051, A112345.

Sequence in context: A280125 A339060 A280586 * A294080 A294019 A123721

Adjacent sequences: A112341 A112342 A112343 * A112345 A112346 A112347

Keyword

nonn

Author

Reinhard Zumkeller, Sep 05 2005

Status

approved