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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime. 6
0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 2, 69, 3, 111, 24, 190, 13, 384, 31, 646, 102, 1212, 113, 2348, 227, 4254, 613, 7993, 976, 15459, 1915, 28825, 4357, 54988, 7868, 105826, 15760, 201115, 33376, 385590, 63974, 744446, 128224, 1428047, 262914, 2754037 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

Circularity means the last part is followed by the first.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

EXAMPLE

The a(2) = 1 through a(10) = 8 necklace compositions:

  (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)      (10)

            (2,2)       (2,4)         (2,6)      (3,6)    (2,8)

                        (3,3)         (4,4)      (3,3,3)  (4,6)

                        (2,2,2)       (2,2,4)             (5,5)

                                      (2,2,2,2)           (2,2,6)

                                                          (2,4,4)

                                                          (2,2,2,4)

                                                          (2,2,2,2,2)

The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).

MATHEMATICA

neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@Not/@CoprimeQ@@@Partition[#, 2, 1, 1]&]], {n, 10}]

PROG

(PARI)

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}

seq(n)={my(v=sum(k=1, n, k*b(n, k, (i, j)->gcd(i, j)<>1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019

CROSSREFS

The non-necklace, non-circular version is A178470.

The version for indivisibility (rather than co-primality) is A328600.

The circularly coprime (as opposed to anti-coprime) version is A328597.

Partitions with no consecutive parts relatively prime are A328187.

Cf. A000031, A000740, A008965, A032153, A318728, A318729, A318748, A328172, A328188, A328220, A328335, A328336, A328601, A328609.

Sequence in context: A200976 A328187 A298971 * A218970 A216952 A114326

Adjacent sequences:  A328599 A328600 A328601 * A328603 A328604 A328605

KEYWORD

nonn

AUTHOR

Gus Wiseman, Oct 25 2019

EXTENSIONS

Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019

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 January 20 05:47 EST 2020. Contains 331067 sequences. (Running on oeis4.)