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,3

Links

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

Formula

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

Example

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

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}]

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

Crossrefs

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

Sequence in context: A117537 A018065 A048818 * A062713 A334630 A086108

Adjacent sequences: A318742 A318743 A318744 * A318746 A318747 A318748

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

Extensions

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

Status

approved