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

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, 195, 1, 2883, 1, 435, 67, 617, 17, 4133, 1, 1177, 135, 2915, 1, 36647, 1, 3299, 1767, 4757, 1, 52045, 13, 21149, 619, 11307, 1, 187307, 69, 29467, 1179, 30461

Offset: 0

Author

Ilya Gutkovskiy, Feb 04 2020

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to compositions

Crossrefs

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

Programs

Maple

a:= proc(n) local b; b:=
      proc(m, i, p) option remember; `if`(m=0, p!, `if`(i<1, 0,
        b(m, i-1, p)+`if`(i>m or igcd(i, n)=1, 0, b(m-i, i-1, p+1))))
      end; forget(b): b(n$2, 0)
    end:
seq(a(n), n=0..63);  # Alois P. Heinz, Feb 04 2020

Mathematica

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]];
a /@ Range[0, 63] (* Jean-François Alcover, Nov 26 2020, after Alois P. Heinz *)