cp's OEIS Frontend

A331887 Number of partitions of n into distinct parts having a common factor > 1 with n.

%I A331887 #15 Jan 26 2025 09:20:29
%S A331887 1,0,1,1,1,1,2,1,2,2,3,1,5,1,5,4,6,1,11,1,11,6,12,1,23,3,18,8,23,1,69,
%T A331887 1,32,13,38,7,84,1,54,19,79,1,224,1,90,46,104,1,264,5,187,39,166,1,
%U A331887 449,14,251,55,256,1,1374,1,340,111,390,20,1692,1,513,105,1610
%N A331887 Number of partitions of n into distinct parts having a common factor > 1 with n.
%H A331887 Antti Karttunen, <a href="/A331887/b331887.txt">Table of n, a(n) for n = 0..10416</a>
%H A331887 <a href="/index/Par#part">Index entries for sequences related to partitions</a>
%F A331887 a(n) = [x^n] Product_{k: gcd(n,k) > 1} (1 + x^k).
%e A331887 a(12) = 5 because we have [12], [10, 2], [9, 3], [8, 4] and [6, 4, 2].
%p A331887 a:= proc(m) option remember; local b; b:=
%p A331887       proc(n, i) option remember; `if`(i*(i+1)/2<n, 0, `if`(n=0, 1,
%p A331887         `if`(igcd(i, m)>1, b(n-i, min(i-1, n-i)), 0)+b(n, i-1)))
%p A331887       end; forget(b); b(m$2)
%p A331887     end:
%p A331887 seq(a(n), n=0..82);  # _Alois P. Heinz_, Jan 30 2020
%t A331887 Table[SeriesCoefficient[Product[(1 + Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 70}]
%o A331887 (PARI) A331887(n) = { my(p = Ser(1, 'x, 1+n)); for(k=2, n, if(gcd(n,k)>1, p *= (1 + 'x^k))); polcoef(p, n); }; \\ _Antti Karttunen_, Jan 25 2025
%Y A331887 Cf. A036998, A121998, A175787 (positions of 1's), A303280, A331885, A331888.
%K A331887 nonn
%O A331887 0,7
%A A331887 _Ilya Gutkovskiy_, Jan 30 2020