A Prime Game:

Write down a multidigit prime number (i.e. a prime number > 10), and I can always strike out 0 or more digits to get a prime in this list:

{11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}

e.g.

• Write down the prime 149 → I can delete the digit 4, to get the prime 19
• Write down the prime 439 → I can delete the digit 9, to get the prime 43
• Write down the prime 857 → I can delete zero digits, to get the prime 857
• Write down the prime 2081 → I can delete the digit 0, to get the prime 281
• Write down the largest known double Mersenne prime 170141183460469231731687303715884105727 (2¹²⁷−1) → I can delete all digits except the third-leftmost 1 and the second-rightmost 3, to get the prime 13
• Write down the largest known Fermat prime 65537 → I can delete the 6 and the 3, to get the prime 557 (also I can choose to delete the 6 and two 5's, to get the prime 37) (also I can choose to delete two 5's and the 3, to get the prime 67) (also I can choose to delete the 6, one 5, and the 7, to get the prime 53)
• Write down the famous repunit prime 1111111111111111111 (with 19 1's) → I can delete 17 1's, to get the prime 11
• Write down the prime 1000000000000000000000000000000000000000000000000000000000007 (which is the next prime after 10⁶⁰) → I can delete all 0's, to get the prime 17
• Write down the prime 95801 → I can delete the 9, to get the prime 5801
• Write down the prime 946969 → I can delete the first 9 and two 6's, to get the prime 499
• Write down the prime 90000000581 → I can delete five 0's, the 5, and the 8, to get the prime 9001
• Write down the prime 8555555555555555555551 → I can delete the 8 and nine 5's, to get the prime 555555555551

Now we extend this prime game to bases other than 10.

The minimal elements (https://en.wikipedia.org/wiki/Minimal_element) (https://mathworld.wolfram.com/MaximalElement.html for maximal element, the dual of minimal element, unfortunely there is no article "minimal element" in mathworld, a minimal element of a set (https://en.wikipedia.org/wiki/Set_(mathematics), https://mathworld.wolfram.com/Set.html) under a partial ordering binary relation (https://en.wikipedia.org/wiki/Binary_relation, https://mathworld.wolfram.com/BinaryRelation.html) is a maximal element of the same set under its converse relation (https://en.wikipedia.org/wiki/Converse_relation), a converse relation of a partial ordering relation must also be a partial ordering relation) of the prime numbers (https://en.wikipedia.org/wiki/Prime_number, https://primes.utm.edu/glossary/xpage/Prime.html, https://www.rieselprime.de/ziki/Prime, https://mathworld.wolfram.com/PrimeNumber.html) which are > b written in the positional numeral system (https://en.wikipedia.org/wiki/Positional_numeral_system) with radix (https://en.wikipedia.org/wiki/Radix, https://primes.utm.edu/glossary/xpage/Radix.html, https://www.rieselprime.de/ziki/Base, https://mathworld.wolfram.com/Radix.html) b, as digit (https://en.wikipedia.org/wiki/Numerical_digit, https://www.rieselprime.de/ziki/Digit, https://mathworld.wolfram.com/Digit.html) strings (https://en.wikipedia.org/wiki/String_(computer_science), https://mathworld.wolfram.com/String.html) under the subsequence (https://en.wikipedia.org/wiki/Subsequence, https://mathworld.wolfram.com/Subsequence.html) ordering (https://en.wikipedia.org/wiki/Partially_ordered_set, https://mathworld.wolfram.com/PartialOrder.html), for 2 ≤ b ≤ 36 (I stop at base 36 since this base is a maximum base for which it is possible to write the numbers with the symbols 0, 1, ..., 9 and A, B, ..., Z, references: http://www.tonymarston.net/php-mysql/converter.html, https://www.dcode.fr/base-36-cipher, http://www.urticator.net/essay/5/567.html, http://www.urticator.net/essay/6/624.html, https://docs.python.org/3/library/functions.html#int, https://reference.wolfram.com/language/ref/BaseForm.html, https://baseconvert.com/, https://www.calculand.com/unit-converter/zahlen.php?og=Base+2-36&ug=1, also see https://primes.utm.edu/notes/words.html for the English words which are prime numbers when viewed as a number base 36), using A−Z to represent digit values 10 to 35.

By the theorem that there are no infinite (https://en.wikipedia.org/wiki/Infinite_set, https://primes.utm.edu/glossary/xpage/Infinite.html, https://mathworld.wolfram.com/InfiniteSet.html) antichains (https://en.wikipedia.org/wiki/Antichain, https://mathworld.wolfram.com/Antichain.html) (i.e. a subset of a partially ordered set such that any two distinct elements in the subset are incomparable (https://en.wikipedia.org/wiki/Comparability, https://mathworld.wolfram.com/ComparableElements.html)) for the subsequence ordering (i.e. the set of the minimal elements of any set under the subsequence ordering must be finite, even if this set is infinite, such as the set of the "prime numbers > b" strings in base b (for a given base b ≥ 2), for the proofs for that there are infinitely many primes, see https://en.wikipedia.org/wiki/Euclid%27s_theorem, https://mathworld.wolfram.com/EuclidsTheorems.html, https://primes.utm.edu/notes/proofs/infinite/, https://primes.utm.edu/notes/proofs/infinite/euclids.html, https://primes.utm.edu/notes/proofs/infinite/topproof.html, https://primes.utm.edu/notes/proofs/infinite/goldbach.html, https://primes.utm.edu/notes/proofs/infinite/kummers.html, https://primes.utm.edu/notes/proofs/infinite/Saidak.html), there must be only finitely such minimal elements in every base b.

Addition (https://en.wikipedia.org/wiki/Addition, https://www.rieselprime.de/ziki/Addition, https://mathworld.wolfram.com/Addition.html) and multiplication (https://en.wikipedia.org/wiki/Multiplication, https://www.rieselprime.de/ziki/Multiplication, https://mathworld.wolfram.com/Multiplication.html) are the basic operations of arithmetic (https://en.wikipedia.org/wiki/Arithmetic, https://www.rieselprime.de/ziki/Arithmetic, https://mathworld.wolfram.com/Arithmetic.html) (which is also the basics of mathematics (https://en.wikipedia.org/wiki/Mathematics, https://www.rieselprime.de/ziki/Mathematics, https://mathworld.wolfram.com/Mathematics.html)). In the addition operation, the identity element (https://en.wikipedia.org/wiki/Identity_element, https://mathworld.wolfram.com/IdentityElement.html) is 0, and all natural numbers > 0 can be written as the sum of many 1’s, and the number 1 cannot be broken up; in the multiplication operation, the identity element is 1, and all natural numbers > 1 can be written as the product of many prime numbers, and the prime numbers cannot be broken up. Also, prime numbers are central in number theory (https://en.wikipedia.org/wiki/Number_theory, https://www.rieselprime.de/ziki/Number_theory, https://mathworld.wolfram.com/NumberTheory.html) because of the fundamental theorem of arithmetic (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic, https://primes.utm.edu/glossary/xpage/FundamentalTheorem.html, https://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html): every natural number greater than 1 is either a prime itself or can be factorized (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html) as a product of primes that is unique up to (https://en.wikipedia.org/wiki/Up_to) their order. Also, primes are the natural numbers n > 1 such that if n divides (https://en.wikipedia.org/wiki/Divides, https://primes.utm.edu/glossary/xpage/Divides.html, https://mathworld.wolfram.com/Divides.html) x×y (x and y are natural numbers), then n divides either x or y (or both). Also, prime numbers are the numbers n such that the ring (https://en.wikipedia.org/wiki/Ring_(mathematics), https://mathworld.wolfram.com/Ring.html) of integers modulo n (https://en.wikipedia.org/wiki/Integers_modulo_n, https://mathworld.wolfram.com/Mod.html) (i.e. the ring Z_n) is a field (https://en.wikipedia.org/wiki/Field_(mathematics), https://mathworld.wolfram.com/Field.html) (also is an integral domain (https://en.wikipedia.org/wiki/Integral_domain, https://mathworld.wolfram.com/IntegralDomain.html), also is a division ring (https://en.wikipedia.org/wiki/Division_ring), also has no zero divisors (https://en.wikipedia.org/wiki/Zero_divisor, https://mathworld.wolfram.com/ZeroDivisor.html) other than 0 (for the special case that n = 1, it is the zero ring (https://en.wikipedia.org/wiki/Zero_ring, https://mathworld.wolfram.com/TrivialRing.html))). Besides, "the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" to "the set of the prime numbers (except b itself) digit strings with length > 1 in base b" to "the partially ordered binary relation by subsequence" is "the set of the prime numbers" to "the set of the integers > 1" to "the partially ordered binary relation by divisibility" (and indeed, the "> 1" in "the prime numbers (except b itself) digit strings with length > 1 in base b" can be corresponded to the "> 1" in "the integers > 1") (for the reason why b itself is excluded (when b is prime, if b is composite, then there is no difference to include the b itself or not), see the sections below and https://mersenneforum.org/showpost.php?p=531632&postcount=7, the main reason is that b is the only prime ending with 0), thus the problem in this article is very important and beautiful.

This problem is an extension of the original minimal prime problem (https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_17.pdf), https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_18.pdf), https://cs.uwaterloo.ca/~cbright/talks/minimal-slides.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_19.pdf), https://doi.org/10.1080/10586458.2015.1064048 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_20.pdf), https://scholar.colorado.edu/downloads/hh63sw661 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_16.pdf), https://github.com/curtisbright/mepn-data, https://github.com/curtisbright/mepn, https://github.com/RaymondDevillers/primes) to cover Conjectures ‘R Us Sierpinski/Riesel conjectures base b (http://www.noprimeleftbehind.net/crus/, http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf)) with k-values < b, i.e. finding the smallest prime of the form k×bⁿ+1 and k×bⁿ−1 (or proving that such prime does not exist) for all k < b (also to cover dual (http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/i61/i61.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_1.pdf), https://www.rechenkraft.net/wiki/Five_or_Bust, https://oeis.org/A076336/a076336c.html, http://www.mit.edu/~kenta/three/prime/dual-sierpinski/ezgxggdm/dualsierp-excerpt.txt, http://mit.edu/kenta/www/three/prime/dual-sierpinski/ezgxggdm/dualsierp.txt.gz, https://mersenneforum.org/showthread.php?t=10761, https://mersenneforum.org/showthread.php?t=6545) Sierpinski/Riesel conjectures base b with k-values < b, i.e. finding the smallest prime of the form bⁿ+k and bⁿ−k (which are the dual forms of k×bⁿ+1 and k×bⁿ−1, respectively) (or proving that such prime does not exist) for all k < b) (also to cover finding the smallest prime of some classic forms (or proving that such prime does not exist), such as bⁿ+2, bⁿ−2, bⁿ+(b−1), bⁿ−(b−1), 2×bⁿ+1, 2×bⁿ−1, (b−1)×bⁿ+1, (b−1)×bⁿ−1, with n ≥ 1, for the same base b (of course, for some bases b the original minimal prime base b problem already covers finding the smallest prime of these forms, e.g. the original minimal prime base b problem covers finding the smallest prime of the form (b−1)×bⁿ+1 if and only if b−1 is not prime, and the original minimal prime base b problem covers finding the smallest prime of the form (b−1)×bⁿ−1 if and only if neither b−1 nor b−2 is prime, but I want the problem covers finding the smallest prime of these forms for all bases b)). The original minimal prime base b problem does not cover Conjectures ‘R Us Sierpinski/Riesel conjectures base b with conjectured k (http://www.noprimeleftbehind.net/crus/tab/CRUS_tab.htm, http://www.noprimeleftbehind.net/crus/vstats/all_ck_sierpinski.txt, http://www.noprimeleftbehind.net/crus/vstats/all_ck_riesel.txt) < b, since in Riesel side, the prime is not minimal prime in original definition if either k−1 or b−1 (or both) is prime, and in Sierpinski side, the prime is not minimal prime in original definition if k is prime (e.g. 25×30³⁴²⁰⁵−1 is not minimal prime in base 30 in original definition, since it is OT₃₄₂₀₅ in base 30, and T (= 29 in decimal) is prime, but it is minimal prime in base 30 if only primes > base are counted), but this extended version of minimal prime base b problem does. (There is someone else who also exclude the single-digit primes, but his research is about substring (https://en.wikipedia.org/wiki/Substring) instead of subsequence, see https://www.mersenneforum.org/showpost.php?p=235383&postcount=42, subsequences can contain consecutive elements which were not consecutive in the original sequence, a subsequence which consists of a consecutive run of elements from the original sequence, such as 234 from 123456, is a substring, substring is a refinement of the subsequence, subsequence is a generalization of substring, substring must be subsequence, but subsequence may not be substring, 514 is a subsequence of 352148, but not a substring of 352148, see the list below of the comparation of "subsequence" and "substring")

However, including the base (b) itself results in automatic elimination of all possible extension numbers with "0 after 1" from the set (when the base is prime, if the base is composite, then there is no difference to include the base (b) itself or not), which is quite restrictive (since when the base is prime, then the base (b) itself is the only prime ending with 0, i.e. having trailing zero (https://en.wikipedia.org/wiki/Trailing_zero), since in any base, all numbers ending with 0 (i.e. having trailing zero) are divisible by the base (b), thus cannot be prime unless it is equal the base (b), i.e. "10" in base b, note that the numbers cannot have leading zero (https://en.wikipedia.org/wiki/Leading_zero), since typically this is not the way we write numbers (in any base), thus for all primes in our sets (i.e. all primes > base (b)), all zero digits must be "between" other digits). (for the reference of this, see https://mersenneforum.org/showpost.php?p=531632&postcount=7)

Besides, this problem is better than the original minimal prime problem since this problem is regardless whether 1 is considered as prime or not, i.e. no matter 1 is considered as prime or not prime (https://primes.utm.edu/notes/faq/one.html, https://primefan.tripod.com/Prime1ProCon.html, https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_24.pdf), http://www.numericana.com/answer/numbers.htm#one), the sets in this problem are the same, while the sets in the original minimal prime problem are different, e.g. in base 10, if 1 is considered as prime, then the set in the original minimal prime problem is {1, 2, 3, 5, 7, 89, 409, 449, 499, 6469, 6949, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049}, while if 1 is not considered as prime, then the set in the original minimal prime problem is {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}, however, in base 10, the set in this problem is always {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}, no matter 1 is considered as prime or not prime.

The third reason for excluding the single-digit primes is that they are trivial like that Conjectures ‘R Us Sierpinski/Riesel conjectures base b requires exponent n ≥ 1 for these primes (see https://mersenneforum.org/showpost.php?p=447679&postcount=27), n = 0 is not acceptable to avoid the trivial primes (e.g. 2×bⁿ+1, 4×bⁿ+1, 6×bⁿ+1, 10×bⁿ+1, 12×bⁿ+1, 16×bⁿ+1, 3×bⁿ−1, 4×bⁿ−1, 6×bⁿ−1, 8×bⁿ−1, 12×bⁿ−1, 14×bⁿ−1, ... cannot be quickly eliminated with n = 0, or the conjectures become much more easy and uninteresting), for the same reason, this minimal prime puzzle requires ≥ b (i.e. ≥ 2 digits) for these primes, single-digit primes are not acceptable to avoid the trivial primes (e.g. families containing digit 2, 3, 5, 7, B, D, H, J, N, T, V, ... cannot be quickly eliminated with the single-digit prime, or the conjectures become much more easy and uninteresting).

The fourth reason for excluding the primes ≤ b is that starting with b+1 makes the formula of the number of possible (first digit,last digit) combo of a minimal prime in base b more simple and smooth number (https://en.wikipedia.org/wiki/Smooth_number, https://mathworld.wolfram.com/SmoothNumber.html), it is (b−1)×eulerphi(b) (https://oeis.org/A062955), where eulerphi is Euler's totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function, https://primes.utm.edu/glossary/xpage/EulersPhi.html, https://mathworld.wolfram.com/TotientFunction.html, https://oeis.org/A000010), since b−1 is the number of possible first digit (except 0, all digits can be first digit), and eulerphi(b) is the number of possible last digit (only digits coprime to b can be last digit), by rule of product, there are (b−1)×eulerphi(b) possible (first digit,last digit) combo, and if start with b, then when b is prime, there is an additional possible (first digit,last digit) combo: (1,0), and hence the formula will be (b−1)×eulerphi(b)+1 if b is prime, or (b−1)×eulerphi(b) if b is composite (the fully formula will be (b−1)×eulerphi(b)+isprime(b) or (b−1)×eulerphi(b)+floor((b−eulerphi(b)) / (b−1))), which is more complex, and if start with 1 (i.e. the original minimal prime problem), the formula is much more complex.

This problem covers finding the smallest prime of these forms in the same base b (or proving that such prime does not exist): (while the original minimal prime problem does not cover some of these forms for some bases (or all bases) b)

(below (as well as the "left b" files), family "12{3}45" means sequence {1245, 12345, 123345, 1233345, 12333345, 123333345, ...}, where the members are expressed as base b strings, like the numbers in https://stdkmd.net/nrr/aaaab.htm, https://stdkmd.net/nrr/abbbb.htm, https://stdkmd.net/nrr/aaaba.htm, https://stdkmd.net/nrr/abaaa.htm, https://stdkmd.net/nrr/abbba.htm, https://stdkmd.net/nrr/abbbc.htm, https://stdkmd.net/nrr/prime/primecount.txt, https://stdkmd.net/nrr/prime/primedifficulty.txt, e.g. 1{3} (in decimal) is the numbers in https://stdkmd.net/nrr/1/13333.htm, and {1}3 (in decimal) is the numbers in https://stdkmd.net/nrr/1/11113.htm, and 1{2}3 (in decimal) is the numbers in https://stdkmd.net/nrr/1/12223.htm)

In fact, this problem covers finding the smallest prime of these form in the same base b: (where x, y, z are any digits in base b)

• x{0}y
• x{y} (unless y = 1) (see https://stdkmd.net/nrr/abbbb.htm)
• {x}y (unless x = 1) (see https://stdkmd.net/nrr/aaaab.htm)
• x{0}yz (unless there is a prime of the form x{0}y or x{0}z)
• xy{0}z (unless there is a prime of the form x{0}z or y{0}z)
• xy{x} (unless either x = 1 or there is a prime of the form y{x} (or both)) (see https://stdkmd.net/nrr/abaaa.htm)
• {x}yx (unless either x = 1 or there is a prime of the form {x}y (or both)) (see https://stdkmd.net/nrr/aaaba.htm)

Proving that "the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" = the set S is equivalent to:

• Prove that all elements in S, when read as base b representation, are primes > b.
• Prove that all proper subsequence of all elements in S, when read as base b representation, which are > b, are composite.
• Prove that all primes > b, when written in base b, contain at least one element in S as subsequence (equivalently, prove that all strings not containing any element in S as subsequence, when read as base b representation, which are > b, are composite).

("the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" = S is proved if and only if all these three problems are proved, i.e. "the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" = S is a theorem if and only if all these three "conjectures" are theorems)

e.g. proving that "the set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering" = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}, is equivalent to:

• Prove that all of 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027 are primes > 10.
• Prove that all proper subsequence of all elements in {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} which are > 10 are composite.
• Prove that all primes > 10 contain at least one element in {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} as subsequence (equivalently, prove that all numbers > 10 not containing any element in {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} as subsequence are composite, since they are contraposition (https://en.wikipedia.org/wiki/Contraposition), P ⟶ Q and ¬Q ⟶ ¬P are logically equivalent (https://en.wikipedia.org/wiki/Logical_equivalence)).

(since for base b = 10, all these three problems are proved, i.e. all they are theorems, thus, "the set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering" = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} is also proved, i.e. "the set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering" = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} is also a theorem)

To solve this problem (i.e. to compute (https://en.wikipedia.org/wiki/Computing) the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering), we need to determine whether a given family contains a prime. In practice, if family x{Y}z (where x and z are strings (may be empty) of digits in base b, Y is a set of digits in base b) could not be ruled out as only containing composites and Y contains two or more digits, then a relatively small prime > b could always be found in this family. Intuitively, this is because there are a large number of small strings in such a family, and at least one is likely to be prime (e.g. there are 2ⁿ⁻² strings of length n in the family 1{3,7}9, and there are over a thousand strings of length 12 in the family 1{3,7}9, thus it is very impossible that these numbers are all composite). In the case Y contains only one digit, this family is of the form x{y}z, and there is only a single string of each length > (the length of x + the length of z), and it is not known if the following decision problem (https://en.wikipedia.org/wiki/Decision_problem, https://mathworld.wolfram.com/DecisionProblem.html) is recursively solvable:

Problem: Given strings x, z, a digit y, and a base b, does there exist a prime number whose base-b expansion is of the form xy_nz for some n ≥ 0? (If we say "yes", then we should find such a prime (the smallest such prime may be very large, e.g. > 10²⁵⁰⁰⁰, and if so, then we should use primality testing programs such as PFGW or LLR to find it, and before using these programs, we should use sieving programs such as srsieve (or sr1/2/5sieve) to remove the numbers either having small prime factors or having algebraic factors) and prove its primality (and if we want to solve the problem in this article, we should check whether this prime is the smallest such prime or not, i.e. prove all smaller numbers of the form xy_nz with n ≥ 0 are composite, usually by trial division or Fermat primality test), and if we say "no", then we should prove that such prime does not exist, may by covering congruence, algebraic factorization, or combine of them)

An algorithm to solve this problem, for example, would allow us to decide if there are any additional Fermat primes (https://en.wikipedia.org/wiki/Fermat_number, https://primes.utm.edu/glossary/xpage/FermatNumber.html, https://www.rieselprime.de/ziki/Fermat_number, https://mathworld.wolfram.com/FermatNumber.html, https://mathworld.wolfram.com/FermatPrime.html) (of the form 2²ⁿ+1) other than the known ones (corresponding to n = 0, 1, 2, 3, 4). To see this, take b = 2, x = 1, y = 0, and z = 0₁₆1. Since if 2ⁿ+1 is prime then n must be a power of two, a prime of the form x{y}z in base b must be a new Fermat prime. Besides, it would allow us to decide if there are infinitely many Mersenne primes (https://en.wikipedia.org/wiki/Mersenne_prime, https://primes.utm.edu/glossary/xpage/MersenneNumber.html, https://primes.utm.edu/glossary/xpage/Mersennes.html, https://www.rieselprime.de/ziki/Mersenne_number, https://www.rieselprime.de/ziki/Mersenne_prime, https://mathworld.wolfram.com/MersenneNumber.html, https://mathworld.wolfram.com/MersennePrime.html) (of the form 2^p−1 with prime p). To see this, take b = 2, x = 𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)), y = 1, and z = 1_n+1, where n is the exponent of the Mersenne prime which we want to know whether it is the largest Mersenne prime or not. Since if 2ⁿ−1 is prime then n must be a prime, a prime of the form x{y}z in base b must be a new Mersenne prime.

(for the references of Fermat primes and Mersenne primes, see http://www.prothsearch.com/fermat.html and http://www.mersenne.org/primes/, respectively)

Some x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families can be proven to contain no primes > b, by covering congruence (http://irvinemclean.com/maths/siercvr.htm, http://web.archive.org/web/20060925100410/http://www.glasgowg43.freeserve.co.uk/siernums.htm, https://web.archive.org/web/20061116164533/http://www.glasgowg43.freeserve.co.uk/brier2.htm, https://sites.google.com/site/robertgerbicz/coveringsets, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/coveringsets, http://www.iakovlev.org/zip/riesel2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_8.pdf), https://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0376583-0/S0025-5718-1975-0376583-0.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_27.pdf), https://www.ams.org/journals/mcom/1983-40-161/S0025-5718-1983-0679453-8/S0025-5718-1983-0679453-8.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_40.pdf), http://yves.gallot.pagesperso-orange.fr/papers/smallbrier.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_48.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_51.pdf), https://arxiv.org/pdf/2209.10646.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_52.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL18/Baczkowski/bacz2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_61.pdf), https://arxiv.org/pdf/1110.4671.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_62.pdf), http://www.primepuzzles.net/problems/prob_029.htm, http://www.primepuzzles.net/problems/prob_036.htm, http://www.primepuzzles.net/problems/prob_049.htm, https://www.rieselprime.de/Related/LiskovetsGallot.htm, https://www.rieselprime.de/Related/RieselTwinSG.htm, https://stdkmd.net/nrr/coveringset.htm, https://stdkmd.net/nrr/9/91113.htm#prime_period, https://stdkmd.net/nrr/9/94449.htm#prime_period, https://stdkmd.net/nrr/9/95559.htm#prime_period, https://en.wikipedia.org/wiki/Covering_set, https://www.rieselprime.de/ziki/Covering_set, https://mathworld.wolfram.com/SierpinskisCompositeNumberTheorem.html), algebraic factorization (https://en.wikipedia.org/w/index.php?title=Factorization&oldid=790838198#Recognizable_patterns, https://mathworld.wolfram.com/PolynomialFactorization.html, https://stdkmd.net/nrr/repunit/repunitnote.htm, https://stdkmd.net/nrr/1/10004.htm#about_algebraic, https://stdkmd.net/nrr/1/10008.htm#about_algebraic, https://stdkmd.net/nrr/1/13333.htm#about_algebraic, https://stdkmd.net/nrr/4/40001.htm#about_algebraic, https://stdkmd.net/nrr/5/53333.htm#about_algebraic, https://stdkmd.net/nrr/5/54444.htm#about_algebraic, https://stdkmd.net/nrr/5/55552.htm#about_algebraic, https://stdkmd.net/nrr/7/79999.htm#about_algebraic, https://stdkmd.net/nrr/8/83333.htm#about_algebraic, https://stdkmd.net/nrr/8/89999.htm#about_algebraic, https://stdkmd.net/nrr/8/88889.htm#about_algebraic, https://stdkmd.net/nrr/9/99991.htm#about_algebraic, https://brnikat.com/nums/cullen_woodall/algebraic.txt, https://www.numberempire.com/factoringcalculator.php (e.g. for the family 3{8} in base 9, type "4*9^n-1", and it will tell you that this form can be factored to (2×3ⁿ−1) × (2×3ⁿ+1))) (which includes difference-of-two-squares factorization (https://en.wikipedia.org/wiki/Difference_of_two_squares) and sum/difference-of-two-nth-powers factorization with odd n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html) and Aurifeuillean factorization (https://en.wikipedia.org/wiki/Aurifeuillean_factorization, https://www.rieselprime.de/ziki/Aurifeuillian_factor, https://mathworld.wolfram.com/AurifeuilleanFactorization.html, http://myfactorcollection.mooo.com:8090/source/cyclo.cpp, http://myfactorcollection.mooo.com:8090/LCD_2_199, http://myfactorcollection.mooo.com:8090/LCD_2_998) of x⁴+4y⁴), or combine of them (https://mersenneforum.org/showthread.php?t=11143, https://www.fq.math.ca/Scanned/33-3/izotov.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_46.pdf), https://doi.org/10.1016/j.jnt.2008.02.004 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_47.pdf)), e.g. (only list the families which all numbers do not contain "prime > b" subsequence) (see post https://mersenneforum.org/showpost.php?p=594923&postcount=231 for the factor pattern for some of these families) (for the case of covering congruence, we can show that the corresponding numbers are > all elements in the sets if the corresponding numbers are > b, thus these factorizations are nontrivial; and for the case of algebraic factorization, we can show that both factors are > 1 if the corresponding numbers are > b, thus these factorizations are nontrivial; for the case of combine of them, we can show that for the part of covering congruence, the corresponding numbers are > all elements in the sets if the corresponding numbers are > b, and for the part of algebraic factorization, both factors are > 1 if the corresponding numbers are > b, thus these factorizations are nontrivial)

(You can see the factorization (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html) of the numbers in these families in factordb (http://factordb.com/), you have to convert them to algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form, and you will find that all numbers in these families have status (http://factordb.com/status.html) either "FF" or "CF", and no numbers in these families have status (http://factordb.com/status.html) "C" (i.e. in http://factordb.com/listtype.php?t=3), e.g. for the family 3{0}95 in base 13, its algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form is 3×13ⁿ⁺²+122, and in factordb you will find that all numbers in this family are divisible by some element of {5,7,17}, see http://factordb.com/index.php?query=3*13%5E%28n%2B2%29%2B122&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show; for the family {7}D in base 21, its algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form is (7×21ⁿ⁺¹+113)/20, and in factordb you will find that all numbers in this family are divisible by some element of {2,13,17}, see http://factordb.com/index.php?query=%287*21%5E%28n%2B1%29%2B113%29%2F20&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base); for the family 30{F}A0F in base 16, its algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form is 49×16ⁿ⁺³−1521, and in factordb you will find that no numbers in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=49*16%5E%28n%2B3%29-1521&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show; for the family 5{1} in base 25, its algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form is (121×25ⁿ−1)/24, and in factordb you will find that no numbers in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=%28121*25%5En-1%29%2F24&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base); for the family {D}5 in base 14, its algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form is 14ⁿ⁺¹−9, and in factordb you will find that all numbers with even n in this family are divisible by 5, and you will find that no numbers with odd n in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers with odd n in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=14%5E%28n%2B1%29-9&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base); for the family 7{9} in base 17, its algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form is (121×17ⁿ−9)/16, and in factordb you will find that all numbers with odd n in this family are divisible by 2, and you will find that no numbers with even n in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers with even n in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=%28121*17%5En-9%29%2F16&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base). In contrast, you can see the factorization of the numbers in unsolved families in base b (which are listed in the "left b" file) in factordb, you will find some numbers in these families which have neither small prime factors (say < 10¹⁶) nor two nearly equal (prime or composite) factors, also you will find some numbers in these families which have no known proper factor (https://en.wikipedia.org/wiki/Proper_factor, https://mathworld.wolfram.com/ProperFactor.html, https://mathworld.wolfram.com/ProperDivisor.html) > 1 (i.e. you will find some numbers in these families with status (http://factordb.com/status.html) "C" (instead of "CF" or "FF") (i.e. in http://factordb.com/listtype.php?t=3) in factordb (http://factordb.com/)), and they have positive Nash weight (https://www.rieselprime.de/ziki/Nash_weight) (or difficulty (https://stdkmd.net/nrr/prime/primedifficulty.txt)), and they have prime candidates, we can use the sense of http://www.iakovlev.org/zip/riesel2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_8.pdf), https://stdkmd.net/nrr/1/10003.htm#prime_period, https://stdkmd.net/nrr/3/30001.htm#prime_period, https://stdkmd.net/nrr/1/13333.htm#prime_period, https://stdkmd.net/nrr/3/33331.htm#prime_period, https://stdkmd.net/nrr/1/11113.htm#prime_period, https://stdkmd.net/nrr/3/31111.htm#prime_period, https://mersenneforum.org/showpost.php?p=138737&postcount=24, https://mersenneforum.org/showpost.php?p=153508&postcount=147, to show this)

Also families which contain only one very small prime > b:

Some x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families could not be proven to contain no primes > b (by covering congruence, algebraic factorization, or combine of them) but no primes > b could be found in the family, even after searching through numbers with over 100000 digits. In such a case, the only way to proceed is to test the primality of larger and larger numbers of such form and hope a prime is eventually discovered.

Many x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families contain no small primes > b even though they do contain very large primes. e.g. the smallest prime in base 13 family 9{5} is 95₁₉₇₄₂₀ which when written in decimal contains 219916 digits (http://www.primenumbers.net/prptop/searchform.php?form=%28113*13%5E197420-5%29%2F12&action=Search), and the smallest prime in base 16 family {3}AF is 3₁₁₆₁₃₇AF which when written in decimal contains 139845 digits (http://www.primenumbers.net/prptop/searchform.php?form=%2816%5E116139%2B619%29%2F5&action=Search), and the smallest prime in base 23 family 9{E} is 9E₈₀₀₈₇₃ which when written in decimal contains 1090573 digits (http://www.primenumbers.net/prptop/searchform.php?form=%28106*23%5E800873-7%29%2F11&action=Search), and the smallest prime in base 25 family 71JD{0}1 is 71JD0₄₅₈₅₄₉1 which when written in decimal contains 641031 digits (http://primes.utm.edu/primes/page.php?id=111834) (this number can be proven prime by N−1 test (https://primes.utm.edu/prove/prove3_1.html, http://factordb.com/nmoverview.php?method=1), since N−1 is trivially fully factored), and the smallest prime in base 32 family NU{0}1 is NU0₆₆₁₈₆₃1 which when written in decimal contains 996208 digits (https://primes.utm.edu/primes/page.php?id=134216) (this number can be proven prime by N−1 test (https://primes.utm.edu/prove/prove3_1.html, http://factordb.com/nmoverview.php?method=1), since N−1 is trivially fully factored), and the smallest prime in base 36 family {P}SZ is P₈₁₉₉₃SZ which when written in decimal contains 127609 digits (http://www.primenumbers.net/prptop/searchform.php?form=%285*36%5E81995%2B821%29%2F7&action=Search) (technically, probable primality tests were used to show this (which have a very small chance of making an error (https://primes.utm.edu/notes/prp_prob.html, https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_22.pdf))) because all known primality tests (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html) run far too slowly to run on a number of this size unless either N−1 (https://primes.utm.edu/prove/prove3_1.html, http://factordb.com/nmoverview.php?method=1) or N+1 (https://primes.utm.edu/prove/prove3_2.html, http://factordb.com/nmoverview.php?method=2) (or both) (unfortunely, none of Wikipedia, Prime Wiki, Mathworld has article for N−1 primality test or N+1 primality test, but a similar article for Pocklington primality test: https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, also see the article for the cyclotomy primality test: https://primes.utm.edu/glossary/xpage/Cyclotomy.html) can be ≥ 1/3 factored (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html) or can be ≥ 1/4 factored and the number is not very large (say not > 10¹⁰⁰⁰⁰⁰), if either N−1 or N+1 (or both) can be ≥ 1/2 factored, then we can use the Pocklington N−1 primality test (https://primes.utm.edu/prove/prove3_1.html, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1) (the N−1 case) or the Morrison N+1 primality test (https://primes.utm.edu/prove/prove3_2.html, http://factordb.com/nmoverview.php?method=2) (the N+1 case), if either N−1 or N+1 (or both) can be ≥ 1/3 factored, then we can use the Brillhart-Lehmer-Selfridge primality test (https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_23.pdf), https://en.wikipedia.org/wiki/Pocklington_primality_test#Extensions_and_variants, http://factordb.com/nmoverview.php?method=3), if either N−1 or N+1 (or both) can be ≥ 1/4 factored but neither can be ≥ 1/3 factored, then we need to use CHG (https://mersenneforum.org/attachment.php?attachmentid=21133&d=1571237465, https://primes.utm.edu/bios/page.php?id=797, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/CHG) to prove its primality (see https://mersenneforum.org/showpost.php?p=528149&postcount=3 and https://mersenneforum.org/showpost.php?p=603181&postcount=438), however, unlike Brillhart-Lehmer-Selfridge primality test for the numbers N such that N−1 or N+1 (or both) can be ≥ 1/3 factored can run for arbitrarily large numbers N (thus, there are no unproven probable primes N such that N−1 or N+1 (or both) can be ≥ 1/3 factored), CHG for the numbers N such that either N−1 or N+1 (or both) can be ≥ 1/4 factored but neither can be ≥ 1/3 factored cannot run for very large N (say > 10¹⁰⁰⁰⁰⁰), for the examples of the numbers which are proven prime by CHG, see https://primes.utm.edu/primes/page.php?id=126454, https://primes.utm.edu/primes/page.php?id=131964, https://primes.utm.edu/primes/page.php?id=123456, https://primes.utm.edu/primes/page.php?id=130933, https://stdkmd.net/nrr/cert/1/ (search for "CHG"), https://stdkmd.net/nrr/cert/2/ (search for "CHG"), https://stdkmd.net/nrr/cert/3/ (search for "CHG"), https://stdkmd.net/nrr/cert/4/ (search for "CHG"), https://stdkmd.net/nrr/cert/5/ (search for "CHG"), https://stdkmd.net/nrr/cert/6/ (search for "CHG"), https://stdkmd.net/nrr/cert/7/ (search for "CHG"), https://stdkmd.net/nrr/cert/8/ (search for "CHG"), https://stdkmd.net/nrr/cert/9/ (search for "CHG"), however, factordb (http://factordb.com/) lacks the ability to verify CHG proofs, see https://mersenneforum.org/showpost.php?p=608362&postcount=165)

The numbers in x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families are of the form (a×bⁿ+c)/gcd(a+c,b−1) for some fixed a, b, c such that a ≥ 1, b ≥ 2 (b is the base), c ≠ 0, gcd(a,c) = 1, gcd(b,c) = 1. Except in the special case c = ±1 and gcd(a+c,b−1) = 1, when n is large the known primality tests for such a number are too inefficient to run. In this case one must resort to a probable primality test such as a Miller–Rabin primality test (https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://primes.utm.edu/glossary/xpage/MillersTest.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html) or a Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html), unless a divisor of the number can be found. Since we are testing many numbers in an exponential sequence, it is possible to use a sieving process (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html) to find divisors rather than using trial division (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html).

To do this, we made use of Geoffrey Reynolds' SRSIEVE software (https://www.bc-team.org/app.php/dlext/?cat=3, http://web.archive.org/web/20160922072340/https://sites.google.com/site/geoffreywalterreynolds/programs/, http://www.rieselprime.de/dl/CRUS_pack.zip, https://primes.utm.edu/bios/page.php?id=905, https://www.rieselprime.de/ziki/Srsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srsieve_1.1.4, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr1sieve_1.4.6, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr2sieve_2.0.0, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srbsieve). This program uses the baby-step giant-step algorithm to find all primes p which divide a×bⁿ+c where p and n lie in a specified range (also, this program was updated so that it also removes the n such that a×bⁿ+c has algebraic factors (e.g. difference-of-two-squares factorization (https://en.wikipedia.org/wiki/Difference_of_two_squares) and sum/difference-of-two-nth-powers factorization with odd n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html) and Aurifeuillean factorization (https://en.wikipedia.org/wiki/Aurifeuillean_factorization, https://www.rieselprime.de/ziki/Aurifeuillian_factor, https://mathworld.wolfram.com/AurifeuilleanFactorization.html, http://myfactorcollection.mooo.com:8090/source/cyclo.cpp, http://myfactorcollection.mooo.com:8090/LCD_2_199, http://myfactorcollection.mooo.com:8090/LCD_2_998) of x⁴+4y⁴), see https://mersenneforum.org/showpost.php?p=452132&postcount=66 and https://mersenneforum.org/showthread.php?t=21916 and https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/srsieve_1.1.4/algebraic.c (note: for the sequence (a×bⁿ+c)/gcd(a+c,b−1), the case of "Mersenne number" in https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/srsieve_1.1.4/algebraic.c is the case which a is rational power of b, c = ±1, gcd(a+c,b−1) ≥ 3, and the case of "GFN" in https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/srsieve_1.1.4/algebraic.c is the case which a is rational power of b, c = 1, gcd(a+c,b−1) is either 1 or 2)). Since this program cannot handle the general case (a×bⁿ+c)/gcd(a+c,b−1) when gcd(a+c,b−1) > 1 we only used it to sieve the sequence a×bⁿ+c for primes p not dividing gcd(a+c,b−1), and initialized the list of candidates to not include n for which there is some prime p dividing gcd(a+c,b−1) for which p dividing (a×bⁿ+c)/gcd(a+c,b−1). The program had to be modified slightly to remove a check which would prevent it from running in the case when a, b, and c were all odd (since then 2 divides a×bⁿ+c, but 2 may not divide (a×bⁿ+c)/gcd(a+c,b−1)) (see https://github.com/curtisbright/mepn-data/commit/1b55b353f46c707bbe52897573914128b3303960).

Once the numbers with small divisors had been removed, it remained to test the remaining numbers using a probable primality test. For this we used the software LLR by Jean Penné (http://jpenne.free.fr/index2.html, https://primes.utm.edu/bios/page.php?id=431, https://www.rieselprime.de/ziki/LLR, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403linux64) or PFGW (https://sourceforge.net/projects/openpfgw/, https://primes.utm.edu/bios/page.php?id=175, https://www.rieselprime.de/ziki/PFGW, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/pfgw_win_4.0.3). Although undocumented, it is possible to run these two programs on numbers of the form (a×bⁿ+c)/gcd(a+c,b−1) when gcd(a+c,b−1) > 1, so this program required no modifications. A script was also written which allowed one to run srsieve while LLR or PFGW was testing the remaining candidates, so that when a divisor was found by srsieve on a number which had not yet been tested by LLR or PFGW it would be removed from the list of candidates.

For the primes < 10²⁵⁰⁰⁰ for the solved or near-solved bases (bases b with ≤ 10 unsolved families, i.e. bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36), we employed PRIMO by Marcel Martin (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/Primo309), an elliptic curve primality proving (https://primes.utm.edu/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://primes.utm.edu/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html, https://primes.utm.edu/top20/page.php?id=27) implementation, to compute primality certificates (https://en.wikipedia.org/wiki/Primality_certificate, https://primes.utm.edu/glossary/xpage/Certificate.html, https://mathworld.wolfram.com/PrimalityCertificate.html, http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/myprimes.html, https://stdkmd.net/nrr/cert/, http://factordb.com/certoverview.php) for the candidates for minimal prime base b which are > 10²⁹⁹ and neither N−1 nor N+1 can be ≥ 1/4 factored.

We have completely solved this problem for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24 (i.e. we have found all minimal primes in these bases and proved that they are all such primes and proved that they are definitely primes (https://en.wikipedia.org/wiki/Provable_prime, http://factordb.com/listtype.php?t=4) (i.e. not merely probable primes)) (thus, currently we can complete the classification of the minimal primes in these bases, and the "minimal prime problem" for these bases are theorems (https://en.wikipedia.org/wiki/Theorem, https://mathworld.wolfram.com/Theorem.html, https://primes.utm.edu/notes/proofs/)), also we have completely solved this problem for bases b = 11, 16, 22, 30 if we allow probable primes (https://en.wikipedia.org/wiki/Probable_prime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, http://factordb.com/listtype.php?t=1) > 10²⁵⁰⁰⁰ in place of proven primes, besides, we have completely solved this problem for bases b = 13, 17, 19, 21, 23, 25, 26, 27, 28, 32, 34, 36 (if we allow strong probable primes in place of proven primes) except the families x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) listed in the "left b" files (see the condensed table below for the searching limit of these families) (thus, currently the "minimal prime problem" for these bases are still unsolved problems (https://en.wikipedia.org/wiki/Open_problem, https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics, https://primes.utm.edu/glossary/xpage/OpenQuestion.html, https://mathworld.wolfram.com/UnsolvedProblems.html, https://primes.utm.edu/notes/conjectures/)).

We are unable to determine if the families x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) listed in the "left b" files (see the condensed table below for the searching limit of these families) contain a prime (only count the numbers > b) or not (even if we allow strong probable primes), i.e. these families have no known prime (or strong probable prime) members > b, nor can they be ruled out as only containing composites (only count the numbers > b) (by covering congruence, algebraic factorization, or combine of them), i.e. whether these families contain a prime or a strong probable prime (only count the numbers > b) are open problems (https://en.wikipedia.org/wiki/Open_problem, https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics, https://primes.utm.edu/glossary/xpage/OpenQuestion.html, https://mathworld.wolfram.com/UnsolvedProblems.html, https://primes.utm.edu/notes/conjectures/), and all of these families are expected to contain a prime > b (in fact, expected to contain infinitely many primes), since there is a heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://primes.utm.edu/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html) that all families which cannot be ruled out as only containing composites or only containing finitely many primes (by covering congruence, algebraic factorization, or combine of them) contain infinitely many primes (references: https://primes.utm.edu/mersenne/heuristic.html, https://primes.utm.edu/notes/faq/NextMersenne.html, https://web.archive.org/web/20100628035147/http://www.math.niu.edu/~rusin/known-math/98/exp_primes), since by the prime number theorem (https://en.wikipedia.org/wiki/Prime_number_theorem, https://primes.utm.edu/glossary/xpage/PrimeNumberThm.html, https://mathworld.wolfram.com/PrimeNumberTheorem.html, https://primes.utm.edu/howmany.html, https://oeis.org/wiki/User:Charles_R_Greathouse_IV/Tables_of_special_primes) the chance (https://en.wikipedia.org/wiki/Probability, https://mathworld.wolfram.com/Probability.html) that a random (https://en.wikipedia.org/wiki/Random_number, https://mathworld.wolfram.com/RandomNumber.html) n-digit base b number is prime is approximately (https://en.wikipedia.org/wiki/Asymptotic_analysis, https://primes.utm.edu/glossary/xpage/AsymptoticallyEqual.html, https://mathworld.wolfram.com/Asymptotic.html) 1/n (more accurately, the chance is approximately 1/(n×ln(b)), where ln is the natural logarithm (https://en.wikipedia.org/wiki/Natural_logarithm, https://primes.utm.edu/glossary/xpage/Log.html, https://mathworld.wolfram.com/NaturalLogarithm.html)). If one conjectures the numbers x{y}z behave similarly you would expect 1/1 + 1/2 + 1/3 + 1/4 + ... = ∞ (https://en.wikipedia.org/wiki/Harmonic_series_(mathematics), https://mathworld.wolfram.com/HarmonicSeries.html) primes of the form x{y}z (of course, this does not always happen, since some x{y}z families can be ruled out as only containing composites (only count the numbers > b) (by covering congruence, algebraic factorization, or combine of them), and every family has its own Nash weight (https://www.rieselprime.de/ziki/Nash_weight) (or difficulty (https://stdkmd.net/nrr/prime/primedifficulty.txt)), families which can be proven to only contain composites or only contain finitely many primes (by covering congruence, algebraic factorization, or combine of them) have Nash weight (or difficulty) 0, and families which cannot be proven to only contain composites or only contain finitely many primes (by covering congruence, algebraic factorization, or combine of them) have positive Nash weight (or difficulty), but it is at least a reasonable conjecture in the absence of evidence to the contrary).

There are also unproven probable primes (however, in this project our results assume that they are in fact primes, since they are > 10²⁵⁰⁰⁰ and the probability that they are in fact composite is < 10⁻²⁰⁰⁰, see https://primes.utm.edu/notes/prp_prob.html and https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_22.pdf)), the unproven probable primes for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36 (the solved or near-solved bases, i.e. the bases b with ≤ 10 unsolved families) are:

All these numbers are strong probable primes (https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://mathworld.wolfram.com/StrongPseudoprime.html) to bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 (see https://oeis.org/A014233), and strong Lucas probable primes (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html) with parameters (P, Q) defined by Selfridge's Method A (see https://oeis.org/A217255), and trial factored to 10¹⁶ (thus, all these numbers are Baillie–PSW probable primes.

Primality certificates (https://en.wikipedia.org/wiki/Primality_certificate, https://primes.utm.edu/glossary/xpage/Certificate.html, https://mathworld.wolfram.com/PrimalityCertificate.html, http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/myprimes.html, https://stdkmd.net/nrr/cert/, http://factordb.com/certoverview.php) for large proven primes (> 10²⁹⁹) for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36 (the solved or near-solved bases, i.e. the bases b with ≤ 10 unsolved families):

Condensed table for bases 2 ≤ b ≤ 36: (the bases b = 11, 13, 16, 17, 19, 21~23, 25~36 data assumes the primality of the probable primes) (This data assumes that a number > 10²⁵⁰⁰⁰ which has passed the Miller–Rabin primality tests to all prime bases p < 64 and has passed the Baillie–PSW primality test and has trial factored to 10¹⁶ is in fact prime, since in some cases (e.g. b = 11) a candidate for minimal prime base b is too large to be proven prime rigorously)