A143325 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1) which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.
1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 8, 6, 0, 1, 4, 15, 24, 15, 0, 1, 5, 24, 60, 80, 27, 0, 1, 6, 35, 120, 255, 232, 63, 0, 1, 7, 48, 210, 624, 1005, 728, 120, 0, 1, 8, 63, 336, 1295, 3096, 4095, 2160, 252, 0, 1, 9, 80, 504, 2400, 7735, 15624, 16320, 6552, 495, 0, 1, 10, 99
Offset: 1
Examples
T(4,2)=6, because 6 words of length 4 over 2-letter alphabet {a,b} are primitive and earlier than others derived by cyclic shifts of the alphabet: aaab, aaba, aabb, abaa, abba, abbb; note that aaaa and abab are not primitive and words beginning with b can be derived by shifts of the alphabet from words in the list; secondly note that the words in the list need not be Lyndon words, for example aaba can be derived from aaab by a cyclic rotation of the positions.
Table begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, ...
0, 3, 8, 15, 24, 35, 48, 63, ...
0, 6, 24, 60, 120, 210, 336, 504, ...
0, 15, 80, 255, 624, 1295, 2400, 4095, ...
0, 27, 232, 1005, 3096, 7735, 16752, 32697, ...
0, 63, 728, 4095, 15624, 46655, 117648, 262143, ...
0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...
Links
Crossrefs
Programs
-
Maple
with(numtheory): f1:= proc(n) option remember; unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k) end; T:= (n,k)-> f1(n)(k); seq(seq(T(n, 1+d-n), n=1..d), d=1..12); -
Mathematica
t[n_, k_] := Sum[k^(d-1)*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 21 2014, from first formula *)
Formula
A339686 a(n) = Sum_{d|n} 6^(d-1).
1, 7, 37, 223, 1297, 7819, 46657, 280159, 1679653, 10078999, 60466177, 362805091, 2176782337, 13060740679, 78364165429, 470185264735, 2821109907457, 16926661132171, 101559956668417, 609359750089711, 3656158440109669, 21936950700844039, 131621703842267137
Offset: 1
Keywords
Links
- Seiichi Manyama, Table of n, a(n) for n = 1..1000
Crossrefs
Programs
-
Magma
A339686:= func< n | (&+[6^(d-1): d in Divisors(n)]) >; [A339686(n): n in [1..40]]; // G. C. Greubel, Jun 25 2024
-
Mathematica
Table[Sum[6^(d - 1), {d, Divisors[n]}], {n, 1, 23}] nmax = 23; CoefficientList[Series[Sum[x^k/(1 - 6 x^k), {k, 1, nmax}], {x, 0, nmax}], x] // Rest -
PARI
a(n) = sumdiv(n, d, 6^(d-1)); \\ Michel Marcus, Dec 13 2020
-
SageMath
def A339686(n): return sum(6^(k-1) for k in (1..n) if (k).divides(n)) [A339686(n) for n in range(1,41)] # G. C. Greubel, Jun 25 2024
Formula
G.f.: Sum_{k>=1} x^k / (1 - 6*x^k).
G.f.: Sum_{k>=1} 6^(k-1) * x^k / (1 - x^k).
a(n) ~ 6^(n-1). - Vaclav Kotesovec, Jun 05 2021
A320090 Number of primitive (=aperiodic) 6-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, 6, 41, 251, 1546, 9281, 55936, 335656, 2015236, 12091631, 72557806, 435346876, 2612129211, 15672776566, 94036939331, 564221643971, 3385331551426, 20311989308806, 121871945977221, 731231675909811, 4387390115926096, 26324340695837771, 157946044538104906
Offset: 1
Keywords
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..1285
Programs
-
Maple
b:= n-> add(`if`(d=n, 6^(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 - 6*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *) -
PARI
a(n) = sum(j=1, n, sumdiv(j, d, 6^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020
Formula
a(n) = Sum_{j=1..n} Sum_{d|j} 6^(d-1) * mu(j/d).
a(n) = A143327(n,6).
a(n) = Sum_{j=1..n} A143325(j,6).
a(n) = A143326(n,6) / 6.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 6*x^k). - Ilya Gutkovskiy, Dec 11 2020
Comments