A318745 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and adjacent parts (including the last with the first part) being coprime.

1, 1, 2, 3, 5, 7, 12, 19, 32, 53, 94, 158, 279, 480, 847, 1487, 2647, 4676, 8349, 14865, 26630, 47700, 85778, 154290, 278318, 502437, 908880, 1645713, 2984546, 5417743, 9847189, 17914494, 32625523, 59467893, 108493134, 198089610, 361965238, 661883231, 1211161991

Offset: 1

Author

Gus Wiseman, Sep 02 2018

Keywords

• nonn

Examples

			The a(7) = 12 Lyndon compositions with adjacent parts coprime:
  (7)
  (16) (25) (34)
  (115)
  (1114) (1213) (1132) (1123)
  (11113) (11212)
  (111112)
		

Links

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

Crossrefs

Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318728, A318731, A318746, A318747.

Programs

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,LyndonQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]

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

Formula

a(n) = A328669(n) + 1 for n > 1. - Andrew Howroyd, Nov 01 2019

Extensions

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