cp's OEIS Frontend

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

%I A100347 #22 Dec 22 2016 09:57:33
%S A100347 1,1,1,3,3,15,3,63,21,125,36,1023,25,4095,314,3357,987,65535,207,
%T A100347 262143,2782,164498,17114,4194303,1705,11349545,119620,7256527,209376,
%U A100347 268435455,1261,1073741823,2178309,276465135,5687872,8460492865,114575,68719476735
%N A100347 Number of compositions of n into parts all relatively prime to n.
%H A100347 Alois P. Heinz, <a href="/A100347/b100347.txt">Table of n, a(n) for n = 0..1000</a>
%F A100347 Coefficient of x^n in expansion of 1/(1-Sum_{d : gcd(d, n)=1} x^d ).
%e A100347 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.
%p A100347 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
%p A100347 # second Maple program:
%p A100347 b:= proc(n, m) option remember; `if`(n=0, 1,
%p A100347       add(`if`(igcd(i, m)>1, 0, b(n-i, m)), i=1..n))
%p A100347     end:
%p A100347 a:= n-> b(n$2):
%p A100347 seq(a(n), n=0..50); # _Alois P. Heinz_, Aug 30 2014
%t A100347 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_ *)
%Y A100347 Cf. A057562.
%K A100347 easy,nonn
%O A100347 0,4
%A A100347 _Vladeta Jovovic_, Dec 29 2004
%E A100347 More terms from _Emeric Deutsch_, Jul 25 2005
%E A100347 a(0) from _Alois P. Heinz_, Aug 30 2014