cp's OEIS Frontend

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

%I A167606 #14 Apr 25 2020 09:58:24
%S A167606 1,1,2,4,7,14,25,48,90,168,316,594,1116,2096,3935,7388,13877,26061,
%T A167606 48944,91919,172623,324188,608827,1143390,2147309,4032677,7573426,
%U A167606 14223008,26711028,50163722,94208254,176924559,332267039,624002605,1171886500,2200820905
%N A167606 Number of compositions of n where each pair of adjacent parts is relatively prime.
%H A167606 Alois P. Heinz, <a href="/A167606/b167606.txt">Table of n, a(n) for n = 0..1000</a>
%F A167606 a(n) ~ c * d^n, where d=1.8780154065731862176678940156530410192010138618103068156064519919669849911..., c=0.5795813856338135589080831265343299561832275012313700387790334792220408848... - _Vaclav Kotesovec_, May 01 2014
%e A167606 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.
%p A167606 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A167606       add(`if`(igcd(i, j)=1, b(n-j, j), 0), j=1..n))
%p A167606     end:
%p A167606 a:= n-> b(n, 1):
%p A167606 seq(a(n), n=0..40);  # _Alois P. Heinz_, Apr 27 2014
%t A167606 b[n_, i_] := b[n, i] = If[n==0, 1, Sum[If[GCD[i, j]==1, b[n-j, j], 0], {j, n}]];
%t A167606 a[n_] := b[n, 1];
%t A167606 a /@ Range[0, 40] (* _Jean-François Alcover_, Apr 25 2020, after _Alois P. Heinz_ *)
%o A167606 (PARI) am(n)={local(r);r=matrix(n,n);
%o A167606 for(k=1,n,
%o A167606 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);
%o A167606 r}
%o A167606 al(n)=local(m);m=am(n);vector(n,k,sum(i=1,k,m[k,i]))
%o A167606 a(left,last=1)={local(r);if(left==0,return(1));
%o A167606 for(k=1,left,if(gcd(k,last)==1,r+=a(left-k,k)));r}
%Y A167606 Cf. A066099, A003242, A032020.
%K A167606 nonn
%O A167606 0,3
%A A167606 _Franklin T. Adams-Watters_, Nov 07 2009