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