The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 7
 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 (list; table; graph; refs; listen; history; text; internal format)
 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: A073496 A176122 A091623 * A309498 A059616 A125053 Adjacent sequences:  A215471 A215472 A215473 * A215475 A215476 A215477 KEYWORD nonn,tabl AUTHOR Peter Luschny, Aug 12 2012 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 20 20:02 EDT 2020. Contains 337265 sequences. (Running on oeis4.)