|
%I #8 Jan 31 2018 04:03:53
%S 0,1,1,2,1,4,1,5,3,8,1,16,1,20,9,35,1,69,1,110,21,188,1,381,7,632,59,
%T 1184,1,2300,1,4115,189,7712,25,14939,1,27596,633,52517,1,101050,1,
%U 190748,2247,364724,1,703331,19,1342283,7713,2581430,1,4985609,193
%N Number of compositions of n that are proper powers of Lyndon words.
%C a(n) is the number of compositions of n that are not Lyndon words but are of the form p * p * ... * p where * is concatenation and p is a Lyndon word.
%F a(n) = Sum_{d|n} (2^d-1)*(phi(n/d)-mu(n/d))/n.
%F a(n) = A008965(n) - A059966(n).
%e The a(12) = 16 compositions: 111111111111, 1111211112, 11131113, 112112112, 11221122, 114114, 12121212, 123123, 131313, 132132, 1515, 222222, 2424, 3333, 444, 66.
%t Table[Sum[DivisorSum[d,MoebiusMu[d/#]*(2^#-1)&]/d,{d,Most@Divisors[n]}],{n,100}]
%o (PARI) a(n) = sumdiv(n, d, (2^d-1)*(eulerphi(n/d)-moebius(n/d))/n); \\ _Michel Marcus_, Jan 31 2018
%Y Cf. A000005, A000031, A000740, A000961, A001045, A008965, A019536, A034691, A051953, A052823, A059966, A060223, A178472, A185700, A296302, A296373.
%K nonn
%O 1,4
%A _Gus Wiseman_, Jan 30 2018
|
