A331885 - OEIS

%I #10 Jan 31 2020 21:50:51

%S 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 152,1,620,1,231,58,298,21,946,1,491,103,921,1,3249,1,1060,325,1256,1,

%U 4866,15,3157,299,2539,1,10369,62,4846,492,4566,1,45786,1,6843

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

%H Alois P. Heinz, <a href="/A331885/b331885.txt">Table of n, a(n) for n = 0..1000</a>

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

%F a(n) = [x^n] Product_{k: gcd(n,k) > 1} 1 / (1 - x^k).

%e a(6) = 4 because we have [6], [4, 2], [3, 3] and [2, 2, 2].

%p a:= proc(m) option remember; local b; b:=

%p       proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,

%p        `if`(igcd(i, m)>1, b(n-i, min(i, n-i)), 0)+b(n, i-1)))

%p       end; forget(b); b(m$2)

%p     end:

%p seq(a(n), n=0..82);  # _Alois P. Heinz_, Jan 30 2020

%t Table[SeriesCoefficient[Product[1/(1 - Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 62}]

%Y Cf. A182986 (positions of 1's), A018783, A057562, A121998, A331887, A331888.

%K nonn

%O 0,5

%A _Ilya Gutkovskiy_, Jan 30 2020