A320088 Number of primitive (=aperiodic) 4-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

1, 4, 19, 79, 334, 1339, 5434, 21754, 87274, 349159, 1397734, 5590954, 22368169, 89472934, 357908119, 1431633559, 5726600854, 22906403494, 91625880229, 366503524969, 1466015148634, 5864060611159, 23456246655574, 93824986622614, 375299963333014, 1501199853398419

Offset

1,2

Links

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

Formula

a(n) = Sum_{j=1..n} Sum_{d|j} 4^(d-1) * mu(j/d).

a(n) = A143327(n,4).

a(n) = Sum_{j=1..n} A143325(j,4).

a(n) = A143326(n,4) / 4.

G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 4*x^k). - Ilya Gutkovskiy, Dec 11 2020

Maple

b:= n-> add(`if`(d=n, 4^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

Mathematica

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 4*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

Prog

(PARI) a(n) = sum(j=1, n, sumdiv(j, d, 4^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

Crossrefs

Column k=4 of A143327.

Partial sums of A295505.

Cf. A008683, A143325, A143326.

Sequence in context: A359087 A037681 A156760 * A122909 A215037 A181300

Adjacent sequences: A320085 A320086 A320087 * A320089 A320090 A320091

Keyword

nonn

Author

Alois P. Heinz, Oct 05 2018

Status

approved