A331887 - OEIS

%I #7 Jan 30 2020 18:15:00

%S 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 1,32,13,38,7,84,1,54,19,79,1,224,1,90,46,104,1,264,5,187,39,166,1,

%U 449,14,251,55,256,1,1374,1,340,111,390,20,1692,1,513,105,1610

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

%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 + x^k).

%e a(12) = 5 because we have [12], [10, 2], [9, 3], [8, 4] and [6, 4, 2].

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

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

%p         `if`(igcd(i, m)>1, b(n-i, min(i-1, 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 + Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 70}]

%Y Cf. A036998, A121998, A175787 (positions of 1's), A303280, A331885, A331888.

%K nonn

%O 0,7

%A _Ilya Gutkovskiy_, Jan 30 2020