# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a178470 Showing 1-1 of 1 %I A178470 #17 Nov 20 2019 09:34:01 %S A178470 1,1,1,1,2,1,5,1,8,4,17,3,38,5,67,25,132,27,290,54,547,163,1086,255, %T A178470 2277,530,4416,1267,8850,2314,18151,4737,35799,10499,71776,20501, %U A178470 145471,41934,289695,89030,581117,178424,1171545,365619,2342563,761051,4699711 %N A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime. %C A178470 A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter. %C A178470 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. %H A178470 Alois P. Heinz, Table of n, a(n) for n = 0..1000 %e A178470 The three compositions for 11 are <11>, <2,6,3> and <3,6,2>. %e A178470 From _Gus Wiseman_, Nov 19 2019: (Start) %e A178470 The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11): %e A178470 1 2 3 4 5 6 7 8 9 A B %e A178470 22 24 26 36 28 263 %e A178470 33 44 63 46 362 %e A178470 42 62 333 55 %e A178470 222 224 64 %e A178470 242 82 %e A178470 422 226 %e A178470 2222 244 %e A178470 262 %e A178470 424 %e A178470 442 %e A178470 622 %e A178470 2224 %e A178470 2242 %e A178470 2422 %e A178470 4222 %e A178470 22222 %e A178470 (End) %p A178470 b:= proc(n, h) option remember; `if`(n=0, 1, %p A178470 add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n)) %p A178470 end: %p A178470 a:= n-> `if`(n=1, 1, b(n, 1)): %p A178470 seq(a(n), n=0..60); # _Alois P. Heinz_, Oct 23 2011 %t A178470 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_ *) %t A178470 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{___,x_,y_,___}/;GCD[x,y]==1]&]],{n,0,20}] (* _Gus Wiseman_, Nov 19 2019 *) %o A178470 (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 %o A178470 al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j])) %Y A178470 The case of partitions is A328187, with Heinz numbers A328336. %Y A178470 Partitions with all pairs of consecutive parts relatively prime are A328172. %Y A178470 Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways). %Y A178470 Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220. %K A178470 nonn %O A178470 0,5 %A A178470 _Franklin T. Adams-Watters_, May 28 2010 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE