A167606 Number of compositions of n where each pair of adjacent parts is relatively prime.

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

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