A112345 -id:A112345 - 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

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

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

A362427 Number of compositions (ordered partitions) of n into perfect powers > 1.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 3, 2, 0, 0, 6, 5, 1, 0, 10, 10, 3, 0, 18, 23, 9, 2, 31, 46, 22, 6, 56, 94, 56, 19, 102, 184, 129, 50, 187, 364, 293, 134, 349, 710, 638, 332, 661, 1384, 1375, 805, 1287, 2683, 2904, 1878, 2547, 5205, 6069, 4306, 5150, 10115, 12530, 9659, 10558

Offset: 0

Ilya Gutkovskiy, Apr 19 2023

nonn

Eric Weisstein's World of Mathematics, Perfect Power.

Cf. A001597, A112344, A112345.

perfectPowerQ[n_] := GCD @@ FactorInteger[n][[;; , 2]] > 1; a[n_] := Total[Multinomial @@ Tally[#][[;; , 2]] & /@ Select[IntegerPartitions[n], AllTrue[#, perfectPowerQ] &]]; Array[a, 50, 0] (* Amiram Eldar, May 05 2023 *)

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A362427 Number of compositions (ordered partitions) of n into perfect powers > 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula