A178470 - OEIS

%I #17 Nov 20 2019 09:34:01

%S 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 2277,530,4416,1267,8850,2314,18151,4737,35799,10499,71776,20501,

%U 145471,41934,289695,89030,581117,178424,1171545,365619,2342563,761051,4699711

%N Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

%C A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.

%C 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 Alois P. Heinz, <a href="/A178470/b178470.txt">Table of n, a(n) for n = 0..1000</a>

%e The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.

%e From _Gus Wiseman_, Nov 19 2019: (Start)

%e The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):

%e   1  2  3  4   5  6    7  8     9    A      B

%e            22     24      26    36   28     263

%e                   33      44    63   46     362

%e                   42      62    333  55

%e                   222     224        64

%e                           242        82

%e                           422        226

%e                           2222       244

%e                                      262

%e                                      424

%e                                      442

%e                                      622

%e                                      2224

%e                                      2242

%e                                      2422

%e                                      4222

%e                                      22222

%e (End)

%p b:= proc(n, h) option remember; `if`(n=0, 1,

%p       add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))

%p     end:

%p a:= n-> `if`(n=1, 1, b(n, 1)):

%p seq(a(n), n=0..60);  # _Alois P. Heinz_, Oct 23 2011

%t 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 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{___,x_,y_,___}/;GCD[x,y]==1]&]],{n,0,20}] (* _Gus Wiseman_, Nov 19 2019 *)

%o (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 al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j]))

%Y The case of partitions is A328187, with Heinz numbers A328336.

%Y Partitions with all pairs of consecutive parts relatively prime are A328172.

%Y Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).

%Y Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.

%K nonn

%O 0,5

%A _Franklin T. Adams-Watters_, May 28 2010