Minimal Elements for the Prime Numbers

ABSTRACT

We say a string of symbols s is minimal for a language L if s is a member of L, and it is not possible to obtain another member of L by striking out one or more symbols from s. Although the set M(L) of minimal strings is necessarily finite, determining it explicitly for a given L can be a difficult computational problem. We use some number-theoretic heuristics to compute M(L), where L is the language of base-b representations of the prime numbers, for 2 ≤ b ≤ 30.

Keywords:

• prime number
• minimal element
• heuristic algorithm

Acknowledgments

We are very grateful to François Morain for proving the primality of 2 · (10¹⁹¹⁵³ − 1)/9 + 77, which enabled us to complete the classification of the minimal elements of primes of the form 4n + 3 in base 10.