A078635 -id:A078635 - cp's OEIS frontend

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

Reinhard Zumkeller, Sep 05 2005

nonn

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

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

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

Cf. A078635 (allowing 1).

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

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 *)

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

Name clarified by Sean A. Irvine, Jan 12 2025

A131799 Number of partitions of n into parts that are squares or cubes.

Original entry on oeis.org

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, 61, 69, 74, 78, 90, 98, 103, 107, 122, 135, 143, 152, 170, 186, 194, 203, 225, 247, 261, 275, 305, 330, 348, 362, 396, 429, 454, 477, 519, 561, 590, 618, 666, 717

Offset: 0

Reinhard Zumkeller, Jul 16 2007

nonn

a(n) = A078635(n) for n < 32 = 2^5.

			a(10) = #{9+1, 8+1+1, 4+4+1+1, 4+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1} = 5.

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

Cf. A000041, A001156, A002760, A003108, A078635.

nmax = 65; c2max = nmax^(1/2); c3max = nmax^(1/3);
s = Flatten[{Table[n^2, {n, 1, c2max}]}~Join~{Table[n^3, {n, 1, c3max}]}];
Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* Robert Price, Jul 31 2020 *)

G.f.: Product_{k>=1} (1 - x^(k^6)) / ((1 - x^(k^2)) * (1 - x^(k^3))). - Vaclav Kotesovec, Jan 12 2017

a(0)=1 prepended by Ilya Gutkovskiy, Jan 11 2017

A284171 Number of partitions of n into distinct perfect powers (including 1).

Original entry on oeis.org

1, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 3, 2, 1, 2, 3, 2, 1, 2, 3, 3, 2, 4, 5, 3, 2, 4, 5, 3, 2, 4, 6, 4, 2, 4, 7, 5, 2, 5, 8, 5, 2, 5, 8, 6, 3, 5, 10, 8, 4, 6, 10, 8, 4, 6, 10, 9, 5, 7, 11, 10, 6, 8, 12, 10, 6, 8, 13, 11, 7, 9, 15, 13, 7, 10, 16, 14, 8, 10, 16, 15, 9, 10, 17, 16, 9, 11

Offset: 0

Ilya Gutkovskiy, Mar 21 2017

nonn

Differs from the sequence A112345 which does not consider 1 as a perfect power.

			a(25) = 3 because we have [25], [16, 9] and [16, 8, 1].

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Perfect Power
Index entries for related partition-counting sequences

Cf. A001597, A078635, A112344, A112345.

nmax = 100; CoefficientList[Series[(1 + x) Product[(1 + Boole[GCD @@ FactorInteger[k][[All, 2]] > 1] x^k), {k, 1, nmax}], {x, 0, nmax}], x]

Vec((1 + x) * prod(k=1, 100, 1 + (gcd(factorint(k)[,2])>1)*x^k) + O(x^101)) \\ Indranil Ghosh, Mar 21 2017

G.f.: Product_{k>=1} (1 + x^A001597(k)).

a(n) = A112345(n-1) + A112345(n).

A282499 Expansion of (Sum_{k = i^j, i>=1, j>=2, excluding duplicates} x^k)^3.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 3, 0, 0, 3, 3, 3, 1, 6, 6, 0, 3, 6, 9, 3, 3, 12, 3, 0, 4, 9, 9, 4, 6, 9, 6, 0, 9, 12, 12, 9, 9, 18, 9, 6, 12, 18, 18, 6, 21, 21, 6, 6, 10, 24, 9, 12, 15, 18, 12, 3, 18, 12, 18, 12, 18, 24, 15, 9, 9, 18, 24, 15, 18, 24, 9, 6, 18, 24, 12, 13, 15, 27, 6, 9, 15, 19, 18, 9, 24, 12, 18, 0, 15, 24, 27, 9, 12, 24, 12, 12

Offset: 0

Ilya Gutkovskiy, Feb 16 2017

nonn

Number of ways to write n as an ordered sum of 3 perfect powers (A001597).

			a(14) = 6 because we have  [9, 4, 1], [9, 1, 4], [4, 9, 1], [4, 1, 9], [1, 9, 4] and [1, 4, 9].

Ilya Gutkovskiy, Extended graphical example
Eric Weisstein's World of Mathematics, Perfect Powers

Cf. A001597, A078635, A113505.

nmax = 95; CoefficientList[Series[(x + Sum[Boole[GCD @@ FactorInteger[k][[All, 2]] > 1] x^k, {k, 2, nmax}])^3, {x, 0, nmax}], x]

G.f.: (Sum_{k = i^j, i>=1, j>=2, excluding duplicates} x^k)^3.

A282500 Expansion of 1/(1 - Sum_{k = i^j, i>=1, j>=2} x^k).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 8, 13, 19, 26, 37, 55, 81, 116, 167, 244, 358, 520, 752, 1091, 1589, 2311, 3354, 4870, 7081, 10298, 14963, 21734, 31580, 45900, 66704, 96919, 140827, 204654, 297413, 432180, 627996, 912565, 1326117, 1927054, 2800260, 4069160, 5913116, 8592675, 12486402, 18144506, 26366614

Offset: 0

Ilya Gutkovskiy, Feb 16 2017

nonn

Number of compositions (ordered partitions) into perfect powers (A001597).

			a(7) = 5 because we have  [4, 1, 1, 1], [1, 4, 1, 1], [1, 1, 4, 1], [1, 1, 1, 4] and [1, 1, 1, 1, 1, 1, 1].

Eric Weisstein's World of Mathematics, Perfect Powers
Index entries for sequences related to compositions

Cf. A001597, A078635, A112344.

nmax = 95; CoefficientList[Series[1/ (1 - x - Sum[Boole[GCD @@ FactorInteger[k][[All, 2]] > 1] x^k, {k, 2, nmax}]), {x, 0, nmax}], x]

G.f.: 1/(1 - Sum_{k = i^j, i>=1, j>=2} x^k).

a(n) ~ c / r^n, where r = 0.68816189979082638501485812136220175833447947220530020978433949588627... and c = 0.4267808681995359684192168334905096310027880655306734537865362460298... . - Vaclav Kotesovec, Feb 17 2017

A286305 Number of partitions of n into powerful parts (A001694).

Original entry on oeis.org

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, 787, 831, 873, 948, 1016, 1071, 1118, 1210, 1296, 1366, 1433

Offset: 0

Ilya Gutkovskiy, May 12 2017

nonn

			a(8) = 4 because we have [8], [4, 4], [4, 1, 1, 1, 1] and [1, 1, 1, 1, 1, 1, 1, 1].

Eric Weisstein's World of Mathematics, Powerful Number
Index entries for sequences related to powerful numbers
Index entries for sequences related to partitions

Cf. A001694, A078635, A286320.

nmax = 75; CoefficientList[Series[1/(1 - x) Product[1/(1 - Boole[Min@ FactorInteger[k][[All, 2]] > 1] x^k), {k, 2, nmax}], {x, 0, nmax}], x]

G.f.: Product_{k>=1} 1/(1 - x^A001694(k)).

a(n) = A078635(n) for n < 72.

A331923 Number of compositions (ordered partitions) of n into distinct perfect powers.

Original entry on oeis.org

1, 1, 0, 0, 1, 2, 0, 0, 1, 3, 2, 0, 2, 8, 6, 0, 1, 4, 6, 0, 2, 12, 24, 0, 2, 9, 8, 1, 8, 32, 30, 2, 7, 10, 32, 8, 11, 44, 150, 30, 34, 40, 18, 26, 20, 68, 78, 126, 56, 169, 80, 30, 40, 116, 294, 144, 162, 226, 182, 128, 66, 338, 348, 752, 199, 1048

Offset: 0

Ilya Gutkovskiy, Feb 01 2020

			a(17) = 4 because we have [16, 1], [9, 8], [8, 9] and [1, 16].

Robert Israel, Table of n, a(n) for n = 0..2600
Index entries for sequences related to compositions

Cf. A001597, A078635, A112345, A282500, A284171, A331844, A331845.

N:= 200: # for a(0)..a(N)
PP:= {1,seq(seq(b^i,i=2..floor(log[b](N))),b=2..floor(sqrt(N)))}:
G:= mul(1+t*x^p, p=PP):
F:= proc(n) local R, k, v;
  R:= normal(coeff(G, x, n));
  add(k!*coeff(R, t, k), k=1..degree(R, t))
end proc:
F(0):= 1:
map(F, [$0..N]); # Robert Israel, Feb 03 2020

M = 200;
PP = Join[{1}, Table[Table[b^i, {i, 2, Floor[Log[b, M]]}], {b, 2, Floor[ Sqrt[M]]}] // Flatten // Union];
G = Product[1 + t x^p, {p, PP}];
a[n_] := Module[{R, k, v}, R = SeriesCoefficient[G, {x, 0, n}]; Sum[k! SeriesCoefficient[R, {t, 0, k}], {k, 1, Exponent[R, t]}]];
a[0] = 1;
a /@ Range[0, M] (* Jean-François Alcover, Oct 25 2020, after Robert Israel *)

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A131799 Number of partitions of n into parts that are squares or cubes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A284171 Number of partitions of n into distinct perfect powers (including 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A282499 Expansion of (Sum_{k = i^j, i>=1, j>=2, excluding duplicates} x^k)^3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A282500 Expansion of 1/(1 - Sum_{k = i^j, i>=1, j>=2} x^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A286305 Number of partitions of n into powerful parts (A001694).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A331923 Number of compositions (ordered partitions) of n into distinct perfect powers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica