A112344 - OEIS

%I #19 Jan 12 2025 15:37:27

%S 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,

%T 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,

%U 48,47,31,30,58,59,44,42,75,68,55,47,91,86,70,67,110,106,81,81,130,134,104

%N Number of partitions of n into perfect powers with each part > 1.

%H Robert Israel, <a href="/A112344/b112344.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectPower.html">Perfect Power</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Partition.html">Partition</a>

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

%p N:= 200: # to get a(1) to a(N)

%p Pows:= {seq(seq(k^p, p=2..floor(log[k](N))),k=2..floor(sqrt(N)))}:

%p 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:

%p seq(g(n,n), n=1..N); # _Robert Israel_, Nov 04 2015

%t M = 200; (* to get a(1) to a(M) *)

%t Pows = Table[k^p, {k, 2, Floor[Sqrt[M]]}, {p, 2, Floor[Log[k, M]]}] // Flatten // Union;

%t g[n_, q_] := g[n, q] = If[n == 0, 1, Plus @@ Table[g[n - r, r], {r, Select[Pows, # <= Min[q, n]&]}]];

%t Table[g[n, n], {n, 1, M}] (* _Jean-François Alcover_, Feb 03 2018, translated from _Robert Israel_'s Maple code *)

%o (PARI) leastp(n) = {while(!ispower(n), n--; if (n==0, return (0))); n;}

%o 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

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

%Y Cf. A078635 (allowing 1).

%K nonn

%O 1,8

%A _Reinhard Zumkeller_, Sep 05 2005

%E Name clarified by _Sean A. Irvine_, Jan 12 2025