A143324 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).
1, 2, 0, 3, 2, 0, 4, 6, 6, 0, 5, 12, 24, 12, 0, 6, 20, 60, 72, 30, 0, 7, 30, 120, 240, 240, 54, 0, 8, 42, 210, 600, 1020, 696, 126, 0, 9, 56, 336, 1260, 3120, 4020, 2184, 240, 0, 10, 72, 504, 2352, 7770, 15480, 16380, 6480, 504, 0, 11, 90, 720, 4032, 16800, 46410, 78120, 65280, 19656, 990, 0
Offset: 1
Examples
T(2,3)=6, because there are 6 primitive words of length 2 over 3-letter alphabet {a,b,c}: ab, ac, ba, bc, ca, cb; note that the non-primitive words aa, bb and cc don't belong to the list; secondly note that the words in the list need not be Lyndon words, for example ba can be derived from ab by a cyclic rotation of the positions.
Table begins:
1, 2, 3, 4, 5, ...
0, 2, 6, 12, 20, ...
0, 6, 24, 60, 120, ...
0, 12, 72, 240, 600, ...
0, 30, 240, 1020, 3120, ...
Links
- Alois P. Heinz, Antidiagonals n = 1..141, flattened
- C. J. Smyth, A coloring proof of a generalisation of Fermat's little theorem, Amer. Math. Monthly 93, No. 6 (1986), pp. 469-471.
- Lucas Vieira Barbosa, Nonclassical Temporal Correlations Under Finite-Memory Constraints, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.
- Index entries for sequences related to Lyndon words
Crossrefs
Programs
-
Maple
with(numtheory): f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k), d=divisors(n)minus{n}), k) end; T:= (n,k)-> f0(n)(k); seq(seq(T(n, 1+d-n), n=1..d), d=1..12); -
Mathematica
f0[n_] := f0[n] = Function [k, k^n - Sum[f0[d][k], {d, Complement[Divisors[n], {n}]}]]; t[n_, k_] := f0[n][k]; Table[Table[t[n, 1 + d - n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)
Formula
T(n,k) = Sum_{d|n} k^d * mu(n/d).
T(n,k) = k^n - Sum_{d
T(n,k) = A143325(n,k) * k.
T(n,k) = A074650(n,k) * n.
So Sum_{d|n} k^d * mu(n/d) == 0 (mod n), this is a generalization of Fermat's little theorem k^p - k == 0 (mod p) for primes p to an arbitrary modulus n (see the Smyth link). - Franz Vrabec, Feb 09 2021
A342858 a(n) is the least integer h such that there exists a Pythagorean triple (x, y, h) that satisfies f(x)+f(y)+f(h)=n where f(m)=A176774(m) is the smallest polygonality of m; a(n) = 0 if no such h exists.
13530, 136, 35, 5, 4510, 10, 100, 45, 51, 1404
Offset: 9
Comments
a(19) > 10^9 if it exists.
It appears that the triples whose sum is 10 (as in the 2nd example below) have legs n^6 = A001014(n), (n^8 - n^4)/2 = A218131(n+1)/2 and (n^8 + n^4)/2 = A071231(n) for n >= 2; they consist of 2 triangular numbers and 1 square number. - Michel Marcus, Apr 12 2021
Examples
a(9) = 13530 with A176774([8778, 10296, 13530]) = [3,3,3]. a(10) = 136 with A176774([64, 120, 136]) = [4,3,3]. a(11) = 35 with A176774([21, 28, 35]) = [3,3,5]. a(12) = 5 with A176774([3, 4, 5]) = [3,4,5]. a(13) = 4510 with A176774([2926, 3432, 4510]) = [3,5,5]. a(14) = 10 with A176774([6, 8, 10]) = [3,8,3]. a(15) = 100 with A176774([28, 96, 100]) = [3,8,4]. a(16) = 45 with A176774([27, 36, 45]) = [10,3,3]. a(17) = 51 with A176774([45, 24, 51]) = [3,9,5]. a(18) = 1404 with A176774([540, 1296, 1404]) = [7,4,7].
Links
- Michel Marcus, Table of n, a(n) for n = 9..10000, with 0 for a(19)
Crossrefs
Programs
-
PARI
tp(n) = if (n<3, [n], my(v=List()); fordiv(2*n, k, if(k<2, next); if(k==n, break); my(s=(2*n/k-4+2*k)/(k-1)); if(denominator(s)==1, listput(v, s))); v = Vec(v); v[#v]); \\ A176774 vsum(v) = vecsum(apply(tp, v)); lista(limp, lim) = {my(vr = vector(limp)); for(u = 2, sqrtint(lim), for(v = 1, u, if (u*u+v*v > lim, break); if ((gcd(u,v) == 1) && (0 != (u-v)%2), for (i = 1, lim, if (i*(u*u+v*v) > lim, break); my(w = [i*(u*u - v*v), i*2*u*v, i*(u*u+v*v)]); my(h = i*(u*u+v*v)); my(sw = vsum(w)); if (sw <= limp, if (vr[sw] == 0, vr[sw] = h, if (h < vr[sw], vr[sw] = h))););););); vector(#vr - 8, k, vr[k+8]);} lista(80, 15000) \\ Michel Marcus, Apr 16 2021
A363916 Array read by descending antidiagonals. A(n, k) = Sum_{d=0..k} A363914(k, d) * n^d.
1, 0, 1, 0, 1, 1, 0, 0, 2, 1, 0, 0, 2, 3, 1, 0, 0, 6, 6, 4, 1, 0, 0, 12, 24, 12, 5, 1, 0, 0, 30, 72, 60, 20, 6, 1, 0, 0, 54, 240, 240, 120, 30, 7, 1, 0, 0, 126, 696, 1020, 600, 210, 42, 8, 1, 0, 0, 240, 2184, 4020, 3120, 1260, 336, 56, 9, 1
Offset: 0
Comments
Examples
Array A(n, k) starts:
[0] 1, 0, 0, 0, 0, 0, 0, 0, 0, ... A000007
[1] 1, 1, 0, 0, 0, 0, 0, 0, 0, ... A019590
[2] 1, 2, 2, 6, 12, 30, 54, 126, 240, ... A027375
[3] 1, 3, 6, 24, 72, 240, 696, 2184, 6480, ... A054718
[4] 1, 4, 12, 60, 240, 1020, 4020, 16380, 65280, ... A054719
[5] 1, 5, 20, 120, 600, 3120, 15480, 78120, 390000, ... A054720
[6] 1, 6, 30, 210, 1260, 7770, 46410, 279930, 1678320, ... A054721
[7] 1, 7, 42, 336, 2352, 16800, 117264, 823536, 5762400, ... A218124
[8] 1, 8, 56, 504, 4032, 32760, 261576, 2097144, 16773120, ... A218125
A000012|A002378| A047928 | A218130 | A218131
A001477,A007531, A061167, A133499, (diagonal A252764)
.
Triangle T(n, k) starts:
[0] 1;
[1] 0, 1;
[2] 0, 1, 1;
[3] 0, 0, 2, 1;
[4] 0, 0, 2, 3, 1;
[5] 0, 0, 6, 6, 4, 1;
[6] 0, 0, 12, 24, 12, 5, 1;
[7] 0, 0, 30, 72, 60, 20, 6, 1;
[8] 0, 0, 54, 240, 240, 120, 30, 7, 1;
Links
- E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Crossrefs
Programs
-
Maple
A363916 := (n, k) -> local d; add(A363914(k, d) * n^d, d = 0 ..k): for n from 0 to 9 do seq(A363916(n, k), k = 0..8) od;
-
SageMath
def A363916(n, k): return sum(A363914(k, d) * n^d for d in range(k + 1)) for n in range(9): print([A363916(n, k) for k in srange(9)]) def T(n, k): return A363916(k, n - k)
Comments