cp's OEIS Frontend

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

%I A112344 #20 Feb 16 2025 08:32:59
%S A112344 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 A112344 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 A112344 48,47,31,30,58,59,44,42,75,68,55,47,91,86,70,67,110,106,81,81,130,134,104
%N A112344 Number of partitions of n into perfect powers with each part > 1.
%H A112344 Robert Israel, <a href="/A112344/b112344.txt">Table of n, a(n) for n = 1..10000</a>
%H A112344 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectPower.html">Perfect Power</a>
%H A112344 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Partition.html">Partition</a>
%e A112344 a(20) = #{16+4, 8+8+4, 8+4+4+4, 4+4+4+4+4} = 4.
%p A112344 N:= 200: # to get a(1) to a(N)
%p A112344 Pows:= {seq(seq(k^p, p=2..floor(log[k](N))),k=2..floor(sqrt(N)))}:
%p A112344 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 A112344 seq(g(n,n), n=1..N); # _Robert Israel_, Nov 04 2015
%t A112344 M = 200; (* to get a(1) to a(M) *)
%t A112344 Pows = Table[k^p, {k, 2, Floor[Sqrt[M]]}, {p, 2, Floor[Log[k, M]]}] // Flatten // Union;
%t A112344 g[n_, q_] := g[n, q] = If[n == 0, 1, Plus @@ Table[g[n - r, r], {r, Select[Pows, # <= Min[q, n]&]}]];
%t A112344 Table[g[n, n], {n, 1, M}] (* _Jean-François Alcover_, Feb 03 2018, translated from _Robert Israel_'s Maple code *)
%o A112344 (PARI) leastp(n) = {while(!ispower(n), n--; if (n==0, return (0))); n;}
%o A112344 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 A112344 Cf. A001597, A000041, A001156, A078134, A062051, A112345.
%Y A112344 Cf. A078635 (allowing 1).
%K A112344 nonn
%O A112344 1,8
%A A112344 _Reinhard Zumkeller_, Sep 05 2005
%E A112344 Name clarified by _Sean A. Irvine_, Jan 12 2025