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,3

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.

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

Formula

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

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

Example

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]

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

Prog

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

Crossrefs

Cf. A056665, A054630, A143328, A215475.

Sequence in context: A176122 A370380 A091623 * A348114 A309498 A059616

Adjacent sequences: A215471 A215472 A215473 * A215475 A215476 A215477

Keyword

nonn,tabl

Author

Peter Luschny, Aug 12 2012

Status

approved