login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

        # print "".join(map(str, a[1:]))

        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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 04:27 EDT 2019. Contains 327995 sequences. (Running on oeis4.)