login
A100347
Number of compositions of n into parts all relatively prime to n.
5
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
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
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