A379957 - OEIS

%I #20 Jan 23 2025 17:43:50

%S 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,

%T 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,

%U 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

%N 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.

%H Antti Karttunen, <a href="/A379957/b379957.txt">Table of n, a(n) for n = 1..20000</a>

%H <a href="/index/Par#part">Index entries for sequences related to partitions</a>.

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

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

%e The a(2) = 1 through a(12) = 9 integer partitions (A = 10, B = 11, C = 12):

%e   (2)  (3)  (4)   (5)  (6)    (7)  (8)     (9)    (A)      (B)  (C)

%e             (22)       (33)        (44)    (333)  (55)          (66)

%e                        (42)        (422)          (82)          (93)

%e                        (222)       (2222)         (442)         (444)

%e                                                   (4222)        (822)

%e                                                   (22222)       (3333)

%e                                                                 (4422)

%e                                                                 (42222)

%e                                                                 (222222)

%e 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.

%o (PARI)

%o powers_of_d_reversed(n, d) = vecsort(vector(logint(n, d), i, d^i),,4);

%o 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));

%o A379957(n) = if(!n,1,sumdiv(n, d, if(1==d, 0, partitions_into_parts(n-d, powers_of_d_reversed(n, d)))));

%o (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)));

%o (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

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

%Y Cf. also A072721, A322900.

%K nonn,new

%O 1,4

%A _Antti Karttunen_, Jan 22 2025