A252764 Number of length n primitive (=aperiodic or period n) n-ary words.

1, 2, 24, 240, 3120, 46410, 823536, 16773120, 387419760, 9999899910, 285311670600, 8916097441680, 302875106592240, 11112006720144330, 437893890380096640, 18446744069414584320, 827240261886336764160, 39346408075098144278664, 1978419655660313589123960

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..350

Formula

a(n) = Sum_{d|n} n^d * mu(n/d), mu = A008683.

a(n) = A075147(n)*n.

a(n) = A074650(n,n) * n.

a(n) = A143325(n,n) * n.

a(n) = A143324(n,n).

Example

a(3) = 24 because there are 24 primitive words of length 3 over 3-letter alphabet {a,b,c}: aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb.

Maple

with(numtheory):
a:= n-> add(n^d *mobius(n/d), d=divisors(n)):
seq(a(n), n=1..25);

Mathematica

a[n_] := DivisorSum[n, n^# * MoebiusMu[n/#]& ];
Array[a, 25] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

Crossrefs

Main diagonal of A143324.

Cf. A008683, A074650, A075147, A143324, A143325.

Sequence in context: A143407 A366155 A228619 * A215929 A132596 A099669

Adjacent sequences: A252761 A252762 A252763 * A252765 A252766 A252767

Keyword

nonn

Author

Alois P. Heinz, Dec 21 2014

Status

approved