login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A167606 Number of compositions of n where each pair of adjacent parts is relatively prime. 26
1, 1, 2, 4, 7, 14, 25, 48, 90, 168, 316, 594, 1116, 2096, 3935, 7388, 13877, 26061, 48944, 91919, 172623, 324188, 608827, 1143390, 2147309, 4032677, 7573426, 14223008, 26711028, 50163722, 94208254, 176924559, 332267039, 624002605, 1171886500, 2200820905 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

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

FORMULA

a(n) ~ c * d^n, where d=1.8780154065731862176678940156530410192010138618103068156064519919669849911..., c=0.5795813856338135589080831265343299561832275012313700387790334792220408848... - Vaclav Kotesovec, May 01 2014

EXAMPLE

For n = 4, there are 8 compositions: [4], [3,1], [2,2], [2,1,1], [1,3], [1,2,1], [1,1,2], and [1,1,1,1]. Of these, only [2,2] has adjacent terms that are not relatively prime, so a(4) = 7.

MAPLE

b:= proc(n, i) option remember; `if`(n=0, 1,

      add(`if`(igcd(i, j)=1, b(n-j, j), 0), j=1..n))

    end:

a:= n-> b(n, 1):

seq(a(n), n=0..40);  # Alois P. Heinz, Apr 27 2014

MATHEMATICA

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[If[GCD[i, j]==1, b[n-j, j], 0], {j, n}]];

a[n_] := b[n, 1];

a /@ Range[0, 40] (* Jean-Fran├žois Alcover, Apr 25 2020, after Alois P. Heinz *)

PROG

(PARI) am(n)={local(r); r=matrix(n, n);

for(k=1, n,

for(i=1, k-1, r[k, i]=sum(j=1, k-i, if(gcd(i, j)==1, r[k-i, j], 0))); r[k, k]=1);

r}

al(n)=local(m); m=am(n); vector(n, k, sum(i=1, k, m[k, i]))

a(left, last=1)={local(r); if(left==0, return(1));

for(k=1, left, if(gcd(k, last)==1, r+=a(left-k, k))); r}

CROSSREFS

Cf. A066099, A003242, A032020.

Sequence in context: A287185 A065491 A072810 * A065455 A220842 A026010

Adjacent sequences:  A167603 A167604 A167605 * A167607 A167608 A167609

KEYWORD

nonn

AUTHOR

Franklin T. Adams-Watters, Nov 07 2009

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 July 13 06:45 EDT 2020. Contains 335675 sequences. (Running on oeis4.)