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
A339688 a(n) = Sum_{d|n} 8^(d-1).
1, 9, 65, 521, 4097, 32841, 262145, 2097673, 16777281, 134221833, 1073741825, 8589967945, 68719476737, 549756076041, 4398046515265, 35184374186505, 281474976710657, 2251799830495305, 18014398509481985, 144115188210078217, 1152921504607109185
Offset: 1
Keywords
Links
- Seiichi Manyama, Table of n, a(n) for n = 1..1000
Crossrefs
Programs
-
Magma
A339688:= func< n | (&+[8^(d-1): d in Divisors(n)]) >; [A339688(n): n in [1..40]]; // G. C. Greubel, Jun 25 2024
-
Mathematica
Table[Sum[8^(d - 1), {d, Divisors[n]}], {n, 1, 21}] nmax = 21; CoefficientList[Series[Sum[x^k/(1 - 8 x^k), {k, 1, nmax}], {x, 0, nmax}], x] // Rest -
PARI
a(n) = sumdiv(n, d, 8^(d-1)); \\ Michel Marcus, Dec 13 2020
-
SageMath
def A339688(n): return sum(8^(k-1) for k in (1..n) if (k).divides(n)) [A339688(n) for n in range(1,41)] # G. C. Greubel, Jun 25 2024
Formula
G.f.: Sum_{k>=1} x^k / (1 - 8*x^k).
G.f.: Sum_{k>=1} 8^(k-1) * x^k / (1 - x^k).
a(n) ~ 8^(n-1). - Vaclav Kotesovec, Jun 05 2021
A320092 Number of primitive (=aperiodic) 8-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, 8, 71, 575, 4670, 37367, 299510, 2396150, 19173302, 153386927, 1227128750, 9817030070, 78536506805, 628292058542, 5026338565487, 40210708557167, 321685685267822, 2573485482143150, 20587883991625133, 164703071933262773, 1317624576539847542
Offset: 1
Keywords
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..1108
Programs
-
Maple
b:= n-> add(`if`(d=n, 8^(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);
-
PARI
a(n) = sum(j=1, n, sumdiv(j, d, 8^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020
Formula
a(n) = Sum_{j=1..n} Sum_{d|j} 8^(d-1) * mu(j/d).
a(n) = A143327(n,8).
a(n) = Sum_{j=1..n} A143325(j,8).
a(n) = A143326(n,8) / 8.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 8*x^k). - Ilya Gutkovskiy, Dec 11 2020
Comments