cp's OEIS Frontend

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.

%I A215474 #22 Mar 04 2020 16:50:19
%S A215474 1,1,3,1,5,14,1,8,32,90,1,14,80,294,829,1,23,196,964,3409,9695,1,41,
%T A215474 508,3304,14569,49685,141280,1,71,1318,11464,63319,259475,861580,
%U A215474 2447592,1,127,3502,40584,280319,1379195,5345276,17360616,49212093,1,226,9382
%N 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.
%C A215474 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.
%D A215474 D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.
%H A215474 Alois P. Heinz, <a href="/A215474/b215474.txt">Rows n = 1..141, flattened</a>
%F A215474 T(n,k) = Sum_{1<=j<=n} (1/j)*Sum_{d|j} mu(j/d)*k^d.
%F A215474 T(n,n) = A143328(n,n).
%e A215474 T(4, 3) counts the 32 ternary preprimes of length 4 which are:
%e A215474 0000,0001,0002,0010,0011,0012,0020,0021,0022,0101,0102,
%e A215474 0110,0111,0112,0120,0121,0122,0202,0210,0211,0212,0220,
%e A215474 0221,0222,1111,1112,1121,1122,1212,1221,1222,2222.
%e A215474 Triangle starts (compare the table A143328 as a square array):
%e A215474 [1]
%e A215474 [1,  3]
%e A215474 [1,  5,  14]
%e A215474 [1,  8,  32,   90]
%e A215474 [1, 14,  80,  294,   829]
%e A215474 [1, 23, 196,  964,  3409,  9695]
%e A215474 [1, 41, 508, 3304, 14569, 49685, 141280]
%p A215474 # From Alois P. Heinz A143328.
%p A215474 with(numtheory):
%p A215474 f0 := proc(n) option remember; unapply(k^n-add(f0(d)(k),d=divisors(n) minus{n}),k) end;
%p A215474 f2 := proc(n) option remember; unapply(f0(n)(x)/n,x) end;
%p A215474 g2 := proc(n) option remember; unapply(add(f2(j)(x),j=1..n),x) end;
%p A215474 A215474 := (n, k) -> g2(n)(k);
%p A215474 seq(print(seq(A215474(n,d),d=1..n)),n=1..8);
%t A215474 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 *)
%o A215474 (Sage)
%o A215474 # This algorithm generates and counts all k-ary n-tuples
%o A215474 # (a_1,..,a_n) such that the string a_1...a_n is preprime.
%o A215474 # It is algorithm F in Knuth 7.2.1.1.
%o A215474 def A215474_count(n, k):
%o A215474     a = [0]*(n+1); a[0]=-1
%o A215474     j = 1; count = 0
%o A215474     while True:
%o A215474         count += 1;
%o A215474         j = n
%o A215474         while a[j] >= k-1 : j -= 1
%o A215474         if j == 0 : break
%o A215474         a[j] += 1
%o A215474         for i in (j+1..n): a[i] = a[i-j]
%o A215474     return count
%o A215474 def A215474(n,k):
%o A215474      return add((1/j)*add(moebius(j/d)*k^d for d in divisors(j))  for j in (1..n))
%o A215474 for n in (1..9): print([A215474(n,k) for k in (1..n)])
%Y A215474 Cf. A056665, A054630, A143328, A215475.
%K A215474 nonn,tabl
%O A215474 1,3
%A A215474 _Peter Luschny_, Aug 12 2012