# 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, 66600049These 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*.

*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*.

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, 65536Shallit 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, ...).

**See Also:** Repunit, LeftTruncatablePrime, RightTruncatablePrime, DeletablePrime, Primeval

**References:**

- Lothaire83 (thm. 6.1.2)
M. Lothaire,"Combinatorics on Words" inEncylopedia 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]

Printed from the PrimePages <t5k.org> © Reginald McLean.