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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for sequences related to compositions

Example

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

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 *)

Crossrefs

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

Sequence in context: A060241 A367951 A337983 * A145015 A085723 A186422

Adjacent sequences: A332000 A332001 A332002 * A332004 A332005 A332006

Keyword

nonn

Author

Ilya Gutkovskiy, Feb 04 2020

Status

approved