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

Links

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

Formula

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

Example

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.

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

Crossrefs

Cf. A057562.

Sequence in context: A286501 A287100 A287188 * A165405 A179857 A260078

Adjacent sequences: A100344 A100345 A100346 * A100348 A100349 A100350

Keyword

easy,nonn

Author

Vladeta Jovovic, Dec 29 2004

Extensions

More terms from Emeric Deutsch, Jul 25 2005

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

Status

approved