A minimal prime is a prime number that when written in a given base , no smaller prime can be formed from a substring of the digits of (the digits need not be consecutive, but they must be in the same order). For example, in base 10, the prime 991 is a minimal prime because all of its possible substrings (9, 9, 1, 99, 91, 91) are either composite or not considered prime. A071062 of Sloane’s OEIS lists the twenty-six base 10 minimal primes.
Clearly, all primes are minimal primes in that base. Such primes are obviously finite, but so are those minimal primes , per Michel Lothaire’s findings. In binary, there are only exactly two minimal primes: 2 and 3, written 10 and 11 respectively. Every larger prime will have 1 as its most significant digit and possibly a 0 somewhere; the 1 and 0 can then be brought together to form 10 (2 in decimal). The exception to this are the Mersenne primes (or binary repunits), but it is even more elegant to prove these are not minimal primes in binary: they contain all smaller Mersenne primes as substrings!
- 1 M. Lothaire “Combinatorics on words” in Encylopedia of mathematics and its applications 17 New York: Addison-Wesley (1983): 238 - 247