A143328
Table T(n,k) read by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary Lyndon words (n,k >= 1) with length less than or equal to n.
Original entry on oeis.org
1, 2, 1, 3, 3, 1, 4, 6, 5, 1, 5, 10, 14, 8, 1, 6, 15, 30, 32, 14, 1, 7, 21, 55, 90, 80, 23, 1, 8, 28, 91, 205, 294, 196, 41, 1, 9, 36, 140, 406, 829, 964, 508, 71, 1, 10, 45, 204, 728, 1960, 3409, 3304, 1318, 127, 1, 11, 55, 285, 1212, 4088, 9695, 14569, 11464, 3502, 226, 1
Offset: 1
T(3,2) = 5, because 5 words of length <=3 over 2-letter alphabet {a,b} are primitive Lyndon words: a, b, ab, aab, abb.
Table begins:
1, 2, 3, 4, 5, ...
1, 3, 6, 10, 15, ...
1, 5, 14, 30, 55, ...
1, 8, 32, 90, 205, ...
1, 14, 80, 294, 829, ...
-
with(numtheory):
f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k),
d=divisors(n)minus{n}), k)
end:
f2:= proc(n) option remember; unapply(f0(n)(x)/n, x) end:
g2:= proc(n) option remember; unapply(add(f2(j)(x), j=1..n), x) end:
T:= (n,k)-> g2(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);
-
f0[n_] := f0[n] = Function[k, k^n-Sum[f0[d][k], {d, Divisors[n]//Most}]]; f2[n_] := f2[n] = Function[x, f0[n][x]/n]; g2[n_] := g2[n] = Function[x, Sum[f2[j][x], {j, 1, n}]]; T[n_, k_] := g2[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)
A215474
Triangle read by rows: number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime.
Original entry on oeis.org
1, 1, 3, 1, 5, 14, 1, 8, 32, 90, 1, 14, 80, 294, 829, 1, 23, 196, 964, 3409, 9695, 1, 41, 508, 3304, 14569, 49685, 141280, 1, 71, 1318, 11464, 63319, 259475, 861580, 2447592, 1, 127, 3502, 40584, 280319, 1379195, 5345276, 17360616, 49212093, 1, 226, 9382
Offset: 1
T(4, 3) counts the 32 ternary preprimes of length 4 which are:
0000,0001,0002,0010,0011,0012,0020,0021,0022,0101,0102,
0110,0111,0112,0120,0121,0122,0202,0210,0211,0212,0220,
0221,0222,1111,1112,1121,1122,1212,1221,1222,2222.
Triangle starts (compare the table A143328 as a square array):
[1]
[1, 3]
[1, 5, 14]
[1, 8, 32, 90]
[1, 14, 80, 294, 829]
[1, 23, 196, 964, 3409, 9695]
[1, 41, 508, 3304, 14569, 49685, 141280]
- D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.
-
# From Alois P. Heinz A143328.
with(numtheory):
f0 := proc(n) option remember; unapply(k^n-add(f0(d)(k),d=divisors(n) minus{n}),k) end;
f2 := proc(n) option remember; unapply(f0(n)(x)/n,x) end;
g2 := proc(n) option remember; unapply(add(f2(j)(x),j=1..n),x) end;
A215474 := (n, k) -> g2(n)(k);
seq(print(seq(A215474(n,d),d=1..n)),n=1..8);
-
t[n_, k_] := Sum[(1/j)*MoebiusMu[j/d]*k^d, {j, 1, n}, {d, Divisors[j]}]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2013 *)
-
# This algorithm generates and counts all k-ary n-tuples
# (a_1,..,a_n) such that the string a_1...a_n is preprime.
# It is algorithm F in Knuth 7.2.1.1.
def A215474_count(n, k):
a = [0]*(n+1); a[0]=-1
j = 1; count = 0
while True:
count += 1;
j = n
while a[j] >= k-1 : j -= 1
if j == 0 : break
a[j] += 1
for i in (j+1..n): a[i] = a[i-j]
return count
def A215474(n,k):
return add((1/j)*add(moebius(j/d)*k^d for d in divisors(j)) for j in (1..n))
for n in (1..9): print([A215474(n,k) for k in (1..n)])
Showing 1-2 of 2 results.
Comments