cp's OEIS Frontend

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.

%I A318745 #12 Nov 01 2019 22:19:15
%S A318745 1,1,2,3,5,7,12,19,32,53,94,158,279,480,847,1487,2647,4676,8349,14865,
%T A318745 26630,47700,85778,154290,278318,502437,908880,1645713,2984546,
%U A318745 5417743,9847189,17914494,32625523,59467893,108493134,198089610,361965238,661883231,1211161991
%N 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.
%H A318745 Andrew Howroyd, <a href="/A318745/b318745.txt">Table of n, a(n) for n = 1..100</a>
%F A318745 a(n) = A328669(n) + 1 for n > 1. - _Andrew Howroyd_, Nov 01 2019
%e A318745 The a(7) = 12 Lyndon compositions with adjacent parts coprime:
%e A318745   (7)
%e A318745   (16) (25) (34)
%e A318745   (115)
%e A318745   (1114) (1213) (1132) (1123)
%e A318745   (11113) (11212)
%e A318745   (111112)
%t A318745 LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
%t A318745 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,LyndonQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]
%o A318745 (PARI)
%o A318745 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, ]}
%o A318745 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
%Y A318745 Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318728, A318731, A318746, A318747.
%K A318745 nonn
%O A318745 1,3
%A A318745 _Gus Wiseman_, Sep 02 2018
%E A318745 Terms a(21) and beyond from _Andrew Howroyd_, Sep 08 2018