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
Keywords
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
Programs
-
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 *) -
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}
Formula
a(n) ~ c * d^n, where d=1.8780154065731862176678940156530410192010138618103068156064519919669849911..., c=0.5795813856338135589080831265343299561832275012313700387790334792220408848... - Vaclav Kotesovec, May 01 2014