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