A379957 Number of partitions of n where the smallest part is a divisor d > 1 of n, and the other parts are positive powers of that divisor.

0, 1, 1, 2, 1, 4, 1, 4, 2, 6, 1, 9, 1, 8, 4, 9, 1, 15, 1, 15, 5, 16, 1, 23, 2, 22, 5, 25, 1, 37, 1, 31, 7, 38, 4, 49, 1, 48, 9, 55, 1, 73, 1, 66, 12, 76, 1, 93, 2, 99, 11, 101, 1, 129, 5, 124, 14, 142, 1, 167, 1, 168, 17, 174, 5, 223, 1, 211, 17, 247, 1, 269, 1, 286, 24, 293, 4, 355, 1, 347, 21, 392, 1, 432, 6, 452, 25

Offset: 1

Author

Antti Karttunen, Jan 22 2025

Keywords

• nonn

Examples

			The a(2) = 1 through a(12) = 9 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)          (93)
                       (222)       (2222)         (442)         (444)
                                                  (4222)        (822)
                                                  (22222)       (3333)
                                                                (4422)
                                                                (42222)
                                                                (222222)
Note how this differs from A072721 first at n=12 (that has value A072721(12)=10 instead of 9) because this doesn't count the partition (84) of 12, as although both 8 and 4 are powers of 2 (which is a divisor of 12), the 2 itself is not included in that partition as its smallest term and 8 is not a power of 4.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000
• Index entries for sequences related to partitions.

Crossrefs

First differs from A322968 at n=16, where a(16) = 9, while A322968(16) = 10.

Cf. also A072721, A322900.

Programs

PARI

powers_of_d_reversed(n, d) = vecsort(vector(logint(n, d), i, d^i),,4);
partitions_into_parts(n, parts, from=1) = if(0==n, 1 , my(s=0); for(i=from, #parts, if(parts[i]<=n, s += partitions_into_parts(n-parts[i], parts, i))); (s));
A379957(n) = if(!n,1,sumdiv(n, d, if(1==d, 0, partitions_into_parts(n-d, powers_of_d_reversed(n, d)))));

PARI

A379957(n) = sumdiv(n, d, if(d>1, polcoef(1/prod(j=1, logint(n,d), 1 - 'x^(d^j), Ser(1, 'x, n-d+1)), n-d)));

PARI

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

Formula

For all n >= 1, a(n) <= A072721(n).

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