A318747 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and adjacent parts (including the last with the first part) being indivisible (either way).

1, 1, 1, 1, 2, 1, 3, 2, 3, 5, 5, 8, 7, 12, 14, 20, 31, 37, 51, 64, 96, 129, 177, 246, 328, 465, 630, 889, 1230, 1692, 2370, 3250, 4587, 6354, 8895, 12384, 17252, 24180, 33777, 47336, 66254, 92752, 130142, 182337, 256246, 359500, 505231, 709787, 997951, 1403883

Offset

1,5

Links

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

Example

The a(14) = 12 Lyndon compositions with adjacent parts indivisible either way:
  (14)
  (3,11) (4,10) (5,9) (6,8)
  (2,5,7) (2,7,5) (3,4,7) (3,7,4)
  (2,3,2,7) (2,3,4,5) (2,5,4,3)

Mathematica

LyndonQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And]&&Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Or[Length[#]==1, And[LyndonQ[#], And@@Not/@Divisible@@@Partition[#, 2, 1, 1], And@@Not/@Divisible@@@Reverse/@Partition[#, 2, 1, 1]]]&]], {n, 20}]

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)->i%j<>0 && j%i<>0))); vector(n, n, 1 + sumdiv(n, d, moebius(d)*v[n/d])/n)} \\ Andrew Howroyd, Nov 01 2019

Crossrefs

Cf. A000740, A008965, A059966, A285573, A303362, A318726, A318727, A318729, A318730, A318731, A318745, A318746.

Sequence in context: A338359 A122545 A072515 * A297367 A118010 A318730

Adjacent sequences: A318744 A318745 A318746 * A318748 A318749 A318750

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

Extensions

Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018

Status

approved