The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime. 14
 1, 1, 1, 1, 2, 1, 5, 1, 8, 4, 17, 3, 38, 5, 67, 25, 132, 27, 290, 54, 547, 163, 1086, 255, 2277, 530, 4416, 1267, 8850, 2314, 18151, 4737, 35799, 10499, 71776, 20501, 145471, 41934, 289695, 89030, 581117, 178424, 1171545, 365619, 2342563, 761051, 4699711 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,5 COMMENTS A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter. a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..1000 EXAMPLE The three compositions for 11 are <11>, <2,6,3> and <3,6,2>. From Gus Wiseman, Nov 19 2019: (Start) The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):   1  2  3  4   5  6    7  8     9    A      B            22     24      26    36   28     263                   33      44    63   46     362                   42      62    333  55                   222     224        64                           242        82                           422        226                           2222       244                                      262                                      424                                      442                                      622                                      2224                                      2242                                      2422                                      4222                                      22222 (End) MAPLE b:= proc(n, h) option remember; `if`(n=0, 1,       add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))     end: a:= n-> `if`(n=1, 1, b(n, 1)): seq(a(n), n=0..60);  # Alois P. Heinz, Oct 23 2011 MATHEMATICA b[n_, h_] := b[n, h] = If[n == 0, 1, Sum [If[h == 1 || GCD[j, h] > 1, b[n - j, j], 0], {j, 2, n}]]; a[n_] := If[n == 1, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *) Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, x_, y_, ___}/; GCD[x, y]==1]&]], {n, 0, 20}] (* Gus Wiseman, Nov 19 2019 *) PROG (PARI) am(n)=local(r); r=matrix(n, n, i, j, i==j); for(i=2, n, for(j=1, i-1, for(k=1, j, if(gcd(i-j, k)>1, r[i, i-j]+=r[j, k])))); r al(n)=local(m); m=am(n); vector(n, i, sum(j=1, i, m[i, j])) CROSSREFS The case of partitions is A328187, with Heinz numbers A328336. Partitions with all pairs of consecutive parts relatively prime are A328172. Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways). Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220. Sequence in context: A064865 A178472 A331888 * A093127 A115123 A132081 Adjacent sequences:  A178467 A178468 A178469 * A178471 A178472 A178473 KEYWORD nonn AUTHOR Franklin T. Adams-Watters, May 28 2010 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 27 12:47 EST 2020. Contains 332306 sequences. (Running on oeis4.)