A332003 - OEIS

%I #9 Nov 26 2020 11:55:50

%S 1,0,1,1,1,1,3,1,3,3,5,1,13,1,13,7,19,1,59,1,59,15,65,1,309,5,133,27,

%T 195,1,2883,1,435,67,617,17,4133,1,1177,135,2915,1,36647,1,3299,1767,

%U 4757,1,52045,13,21149,619,11307,1,187307,69,29467,1179,30461

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

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

%H <a href="/index/Com#comp">Index entries for sequences related to compositions</a>

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

%p a:= proc(n) local b; b:=

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

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

%p       end; forget(b): b(n$2, 0)

%p     end:

%p seq(a(n), n=0..63);  # _Alois P. Heinz_, Feb 04 2020

%t a[n_] := Module[{b}, b[m_, i_, p_] := b[m, i, p] = If[m == 0, p!, If[i < 1, 0, b[m, i - 1, p] + If[i > m || GCD[i, n] == 1, 0, b[m - i, i - 1, p + 1]]]]; b[n, n, 0]];

%t a /@ Range[0, 63] (* _Jean-François Alcover_, Nov 26 2020, after _Alois P. Heinz_ *)

%Y Cf. A032020, A100347, A121998, A178472, A331885, A331887, A331888, A332002.

%K nonn

%O 0,7

%A _Ilya Gutkovskiy_, Feb 04 2020