A328670 Number of aperiodic compositions of n where every pair of adjacent parts (including the last with the first) is relatively prime.

1, 0, 2, 5, 11, 20, 41, 75, 147, 272, 533, 976, 1881, 3490, 6616, 12378, 23405, 43781, 82536, 154709, 291043, 546139, 1026685, 1927038, 3621004, 6798417, 12770935, 23980791, 45042957, 84584416, 158863805, 298336153, 560302805, 1052234995, 1976157456, 3711209272

Offset

1,3

Comments

A sequence is aperiodic if all of its cyclic rotations are different.

Links

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

Example

The a(1) = 1 through a(6) = 20 compositions (empty column not shown):
  (1)  (12)  (13)   (14)    (15)
       (21)  (31)   (23)    (51)
             (112)  (32)    (114)
             (121)  (41)    (123)
             (211)  (113)   (132)
                    (131)   (141)
                    (311)   (213)
                    (1112)  (231)
                    (1121)  (312)
                    (1211)  (321)
                    (2111)  (411)
                            (1113)
                            (1131)
                            (1311)
                            (3111)
                            (11112)
                            (11121)
                            (11211)
                            (12111)
                            (21111)

Mathematica

aperQ[q_]:=Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], aperQ[#]&&And@@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, b(n, k, (i, j)->gcd(i, j)==1))); vector(n, n, sumdiv(n, d, moebius(d)*v[n/d]))} \\ Andrew Howroyd, Nov 01 2019

Crossrefs

The non-aperiodic version is A328609 or A318748 (with singletons).

The non-aperiodic, non-circular version is A167606.

The Lyndon word case is A328669.

Lyndon compositions are A059966, with relatively prime case A318731.

Cf. A000031, A000740, A008965, A318728, A328172, A328597, A328601, A328602.

Sequence in context: A256310 A026390 A005575 * A294745 A352234 A332063

Adjacent sequences: A328667 A328668 A328669 * A328671 A328672 A328673

Keyword

nonn

Author

Gus Wiseman, Oct 29 2019

Extensions

Terms a(21) and beyond from Andrew Howroyd, Nov 01 2019

Status

approved