login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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