login
A298971
Number of compositions of n that are proper powers of Lyndon words.
5
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, 1184, 1, 2300, 1, 4115, 189, 7712, 25, 14939, 1, 27596, 633, 52517, 1, 101050, 1, 190748, 2247, 364724, 1, 703331, 19, 1342283, 7713, 2581430, 1, 4985609, 193
OFFSET
1,4
COMMENTS
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.
FORMULA
a(n) = Sum_{d|n} (2^d-1)*(phi(n/d)-mu(n/d))/n.
a(n) = A008965(n) - A059966(n).
EXAMPLE
The a(12) = 16 compositions: 111111111111, 1111211112, 11131113, 112112112, 11221122, 114114, 12121212, 123123, 131313, 132132, 1515, 222222, 2424, 3333, 444, 66.
MATHEMATICA
Table[Sum[DivisorSum[d, MoebiusMu[d/#]*(2^#-1)&]/d, {d, Most@Divisors[n]}], {n, 100}]
PROG
(PARI) a(n) = sumdiv(n, d, (2^d-1)*(eulerphi(n/d)-moebius(n/d))/n); \\ Michel Marcus, Jan 31 2018
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 30 2018
STATUS
approved