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,4

Links

Antti Karttunen, Table of n, a(n) for n = 1..20000

Index entries for sequences related to partitions.

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

Example

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.

Prog

(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

Crossrefs

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

Cf. also A072721, A322900.

Sequence in context: A286518 A029205 A229340 * A322968 A072721 A380473

Adjacent sequences: A379954 A379955 A379956 * A379958 A379959 A379960

Keyword

nonn,new

Author

Antti Karttunen, Jan 22 2025

Status

approved