|
|
A167606
|
|
Number of compositions of n where each pair of adjacent parts is relatively prime.
|
|
60
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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):
|
|
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];
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|