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