A100347 Number of compositions of n into parts all relatively prime to n.

1, 1, 1, 3, 3, 15, 3, 63, 21, 125, 36, 1023, 25, 4095, 314, 3357, 987, 65535, 207, 262143, 2782, 164498, 17114, 4194303, 1705, 11349545, 119620, 7256527, 209376, 268435455, 1261, 1073741823, 2178309, 276465135, 5687872, 8460492865, 114575, 68719476735

Offset: 0

Author

Vladeta Jovovic, Dec 29 2004

Keywords

• easy
• nonn

Examples

			a(4) = 3 because among the eight compositions of 4 (namely, 1111, 112, 121, 211, 22, 13, 31 and 4) only 1111, 13 and 31 have parts all relatively prime to 4.
		

Links

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

Crossrefs

Cf. A057562.

Programs

Maple

RP:=proc(n) local A, j: A:={}: for j from 1 to n do if gcd(j, n)=1 then A:=A union {j} fi od: A end: a:=proc(n) local S, j, ser: S:=1/(1-sum(x^RP(n)[j], j=1..nops(RP(n)))): ser:=series(S, x=0, n+5): coeff(ser, x^n): end: 1, seq(a(n), n=1..40); # Emeric Deutsch, Jul 25 2005
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      add(`if`(igcd(i, m)>1, 0, b(n-i, m)), i=1..n))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..50); # Alois P. Heinz, Aug 30 2014

Mathematica

b[n_, m_] := b[n, m] = If[n == 0, 1, Sum[If[GCD[i, m] > 1, 0, b[n - i, m]], {i, 1, n}]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Dec 22 2016, after Alois P. Heinz *)

Formula

Coefficient of x^n in expansion of 1/(1-Sum_{d : gcd(d, n)=1} x^d ).

Extensions

More terms from Emeric Deutsch, Jul 25 2005

a(0) from Alois P. Heinz, Aug 30 2014