A072721 Number of partitions of n into parts which are each positive powers of a single number >1 (which may vary between partitions).

1, 0, 1, 1, 2, 1, 4, 1, 4, 2, 6, 1, 10, 1, 8, 4, 10, 1, 15, 1, 17, 5, 16, 1, 26, 2, 22, 5, 29, 1, 37, 1, 36, 7, 38, 4, 57, 1, 48, 9, 65, 1, 73, 1, 77, 13, 76, 1, 108, 2, 99, 11, 117, 1, 130, 5, 145, 14, 142, 1, 189, 1, 168, 19, 202, 5, 223, 1, 241, 17, 247, 1, 309, 1, 286, 24, 333, 4

Offset: 0

Author

Henry Bottomley, Jul 05 2002

Keywords

• nonn

Comments

First differs from A322968 at a(12) = 10, A322968(12) = 9.

Examples

			a(5)=1 since the only partition without 1 as a part is 5 (a power of 5). a(6)=4 since 6 can be written as 6 (powers of 6), 3+3 (powers of 3) and 4+2 and 2+2+2 (both powers of 2).
From _Gus Wiseman_, Jan 01 2019: (Start)
The a(2) = 1 through a(12) = 10 integer partitions (A = 10, B = 11, C = 12):
  (2)  (3)  (4)   (5)  (6)    (7)  (8)     (9)    (A)      (B)  (C)
            (22)       (33)        (44)    (333)  (55)          (66)
                       (42)        (422)          (82)          (84)
                       (222)       (2222)         (442)         (93)
                                                  (4222)        (444)
                                                  (22222)       (822)
                                                                (3333)
                                                                (4422)
                                                                (42222)
                                                                (222222)
(End)
Compare above to the example section of A379957. - _Antti Karttunen_, Jan 23 2025
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to partitions.

Crossrefs

Cf. A018819, A023894, A052410, A072720, A072721, A102430, A175082, A322900, A322902, A322903, A322968.

Cf. also A379957.

Programs

Mathematica

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Table[Length[Select[IntegerPartitions[n],And[FreeQ[#,1],SameQ@@radbase/@#]&]],{n,30}] (* Gus Wiseman, Jan 01 2019 *)

PARI

a(n)={if(n==0, 1, sumdiv(n, d, if(d>1&&!ispower(d), polcoef(1/prod(j=1, logint(n, d), 1 - x^(d^j), Ser(1, x, 1+n)), n))))} \\ Andrew Howroyd, Jan 23 2025

PARI

seq(n)={Vec(1 + sum(d=2, n, if(!ispower(d), -1 + 1/prod(j=1, logint(n, d), 1 - x^(d^j), Ser(1, x, 1+n)))))} \\ Andrew Howroyd, Jan 23 2025

Formula

a(n) = A072721(n)-A072721(n-1). a(p)=1 for p prime.

a(n) = A322900(n) - 1. - Gus Wiseman, Jan 01 2019

G.f.: 1 + Sum_{k>=2} -1 + 1/Product_{j>=1} (1 - x^(A175082(k)^j)). - Andrew Howroyd, Jan 23 2025

For n >= 1, a(n) >= A379957(n). - Antti Karttunen, Jan 23 2025