login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A100347 Number of compositions of n into parts all relatively prime to n. 2
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 16:40 EST 2019. Contains 319271 sequences. (Running on oeis4.)