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.

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

Author

Peter Luschny, Aug 12 2012

Keywords

• nonn
• tabl

Comments

A string is prime if it is nonempty and lexicographically less than all of its proper suffixes. A string is preprime if it is a nonempty prefix of a prime, on some alphabet. See the Knuth reference, section 7.2.1.1.

Examples

			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]
		

References

• D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

Cf. A056665, A054630, A143328, A215475.

Programs

Maple

# 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);

Mathematica

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 *)

Sage

# 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)])

Formula

T(n,k) = Sum_{1<=j<=n} (1/j)*Sum_{d|j} mu(j/d)*k^d.

T(n,n) = A143328(n,n).