login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 1 17:45 EDT 2020. Contains 337444 sequences. (Running on oeis4.)