minimal prime

Every prime number, when written in base ten, has one of the following primes as a subsequence (defined below):

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049

These are the minimal primes. Below we will explain this more fully, list the minimal composites, and offer a few problems for you to solve.

In 1996, Jeffrey Shallit [Shallit96] suggested that we view prime numbers (when written in radix 10) as strings of digits. He then used concepts from formal language theory to define an interesting set of primes called the minimal primes:

A string a is a subsequence of another string b, if a can be obtained from b by deleting zero or more of the characters in b. For example, 514 is a subsequence of 251664. The empty string is a subsequence of every string.
Two strings a and b are comparable if either a is a subsequence of b, or b is a subsequence of a.

A surprising result from formal language theory is that every set of pairwise incomparable strings is finite [Lothaire83]. This means that from any set of strings we can find its minimal elements.

A string a in a set of strings S is minimal if whenever b (an element of S) is a subsequence of a, we have b = a.

This set must be finite!

For example, if our set is the set of prime numbers (written in radix 10), then we get the set of minimal primes listed above. If we take the set of composite numbers (again in base 10) we get the minimal set:

4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70 72, 75, 77, 111, 117, 171, 371, 711, 713, 731.

Shallit conjectures the minimal set for the powers of 2 (in radix 10) is

1, 2, 4, 8, 65536

Shallit left as a challenge to his readers the task of finding minimal sets for the primes in other radices, and for all the other classical sets (Mersenne primes, Fermat primes, ...).

References:

Lothaire83 (thm. 6.1.2)
M. Lothaire,"Combinatorics on Words" in Encylopedia of mathematics and its applications. Vol, 17, Addison-Wesley, 1983. pp. xix+238, ISBN 0-201-13516-7. MR 84g:05002
Shallit96
J. Shallit, "Minimal primes," J. Recreational Math., 30:2 (1999--2000) 113--117. [Available on-line from http://www.cs.uwaterloo.ca/~shallit/papers.html]