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

%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