cp's OEIS Frontend

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

%I A332003 #9 Nov 26 2020 11:55:50
%S A332003 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 A332003 195,1,2883,1,435,67,617,17,4133,1,1177,135,2915,1,36647,1,3299,1767,
%U A332003 4757,1,52045,13,21149,619,11307,1,187307,69,29467,1179,30461
%N A332003 Number of compositions (ordered partitions) of n into distinct parts having a common factor > 1 with n.
%H A332003 Alois P. Heinz, <a href="/A332003/b332003.txt">Table of n, a(n) for n = 0..1000</a>
%H A332003 <a href="/index/Com#comp">Index entries for sequences related to compositions</a>
%e A332003 a(6) = 3 because we have [6], [4, 2] and [2, 4].
%p A332003 a:= proc(n) local b; b:=
%p A332003       proc(m, i, p) option remember; `if`(m=0, p!, `if`(i<1, 0,
%p A332003         b(m, i-1, p)+`if`(i>m or igcd(i, n)=1, 0, b(m-i, i-1, p+1))))
%p A332003       end; forget(b): b(n$2, 0)
%p A332003     end:
%p A332003 seq(a(n), n=0..63);  # _Alois P. Heinz_, Feb 04 2020
%t A332003 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 A332003 a /@ Range[0, 63] (* _Jean-François Alcover_, Nov 26 2020, after _Alois P. Heinz_ *)
%Y A332003 Cf. A032020, A100347, A121998, A178472, A331885, A331887, A331888, A332002.
%K A332003 nonn
%O A332003 0,7
%A A332003 _Ilya Gutkovskiy_, Feb 04 2020