cp's OEIS Frontend

A331888 Number of compositions (ordered partitions) of n into parts having a common factor > 1 with n.

%I A331888 #9 Feb 01 2020 23:15:14
%S A331888 1,0,1,1,2,1,5,1,8,4,17,1,60,1,65,19,128,1,800,1,683,67,1025,1,11005,
%T A331888 16,4097,256,9203,1,369426,1,32768,1027,65537,79,2124475,1,262145,
%U A331888 4099,1424118,1,48987720,1,2127107,96334,4194305,1,411836297,64,67919981,65539
%N A331888 Number of compositions (ordered partitions) of n into parts having a common factor > 1 with n.
%H A331888 Alois P. Heinz, <a href="/A331888/b331888.txt">Table of n, a(n) for n = 0..1000</a>
%H A331888 <a href="/index/Com#comp">Index entries for sequences related to compositions</a>
%F A331888 a(n) = [x^n] 1 / (1 - Sum_{k: gcd(n,k) > 1} x^k).
%e A331888 a(9) = 4 because we have [9], [6, 3], [3, 6] and [3, 3, 3].
%p A331888 a:= proc(m) option remember; local b; b:=
%p A331888       proc(n) option remember; `if`(n=0, 1,
%p A331888         add(`if`(igcd(j, m)>1, b(n-j), 0), j=1..n))
%p A331888       end; forget(b); b(m$2)
%p A331888     end:
%p A331888 seq(a(n), n=0..82);  # _Alois P. Heinz_, Jan 30 2020
%t A331888 Table[SeriesCoefficient[1/(1 - Sum[Boole[GCD[k, n] > 1] x^k, {k, 1, n}]), {x, 0, n}], {n, 0, 51}]
%Y A331888 Cf. A182986 (positions of 1's), A100347, A121998, A178472, A331885, A331887.
%K A331888 nonn
%O A331888 0,5
%A A331888 _Ilya Gutkovskiy_, Jan 30 2020