cp's OEIS Frontend

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

%I A331885 #10 Jan 31 2020 21:50:51
%S A331885 1,0,1,1,2,1,4,1,5,3,8,1,16,1,16,9,22,1,51,1,51,17,57,1,147,7,102,30,
%T A331885 152,1,620,1,231,58,298,21,946,1,491,103,921,1,3249,1,1060,325,1256,1,
%U A331885 4866,15,3157,299,2539,1,10369,62,4846,492,4566,1,45786,1,6843
%N A331885 Number of partitions of n into parts having a common factor > 1 with n.
%H A331885 Alois P. Heinz, <a href="/A331885/b331885.txt">Table of n, a(n) for n = 0..1000</a>
%H A331885 <a href="/index/Par#part">Index entries for sequences related to partitions</a>
%F A331885 a(n) = [x^n] Product_{k: gcd(n,k) > 1} 1 / (1 - x^k).
%e A331885 a(6) = 4 because we have [6], [4, 2], [3, 3] and [2, 2, 2].
%p A331885 a:= proc(m) option remember; local b; b:=
%p A331885       proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
%p A331885        `if`(igcd(i, m)>1, b(n-i, min(i, n-i)), 0)+b(n, i-1)))
%p A331885       end; forget(b); b(m$2)
%p A331885     end:
%p A331885 seq(a(n), n=0..82);  # _Alois P. Heinz_, Jan 30 2020
%t A331885 Table[SeriesCoefficient[Product[1/(1 - Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 62}]
%Y A331885 Cf. A182986 (positions of 1's), A018783, A057562, A121998, A331887, A331888.
%K A331885 nonn
%O A331885 0,5
%A A331885 _Ilya Gutkovskiy_, Jan 30 2020