A298971 Number of compositions of n that are proper powers of Lyndon words.

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.

Links

Table of n, a(n) for n=1..55.

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

Crossrefs

Cf. A000005, A000031, A000740, A000961, A001045, A008965, A019536, A034691, A051953, A052823, A059966, A060223, A178472, A185700, A296302, A296373.

Sequence in context: A200976 A328187 A331885 * A328602 A218970 A216952

Adjacent sequences: A298968 A298969 A298970 * A298972 A298973 A298974

Keyword

nonn

Author

Gus Wiseman, Jan 30 2018

Status

approved