A112344 Number of partitions of n into perfect powers with each part > 1.
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
Keywords
Examples
a(20) = #{16+4, 8+8+4, 8+4+4+4, 4+4+4+4+4} = 4.
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
Programs
-
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 *) -
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
Extensions
Name clarified by Sean A. Irvine, Jan 12 2025