Athena problem

Subject classification: this is a mathematics resource.

Athena problem is an unsolved problem in number theory and formal language theory and order theory, this problem is named after the ancient Greek goddess Athena (which is associated with wisdom). Athena problem is: Give a natural number b > 1, find the set of the minimal elements of the set of the "prime number > b" digit strings in the positional numeral system with base b for the subsequence ordering. (A string x is a subsequence of another string y, if x can be obtained from y by deleting zero or more of the characters in y. For example, 514 is a subsequence of 352148, "string" is a subsequence of "meistersinger". In contrast, 758 is not a subsequence of 378259, "abc" is not a subsequence of "cbacacba", since the characters must be in the same order) (Unlike substring, subsequence is not required to occupy consecutive positions within the original sequences, e.g. the longest common subsequence problem is different from the longest common substring problem)

Using formal language theory terminology, Athena problem is finding the set of the minimal elements of the language of base-b representations of the prime numbers > b (which is a set of strings of symbols over the alphabet Σ_b := {0, 1, ..., b−1}), under the subsequence ordering (i.e. the binary relation "is a subsequence of", which is a partial ordering), for a given natural number b > 1. (You can draw this partial ordering as a Hasse diagram to find all minimal elements)

By Higman's lemma, there are no infinite antichains for the subsequence ordering (i.e. the subsequence ordering is always a well quasi order) (i.e. under the subsequence ordering (i.e. the binary relation "is a subsequence of", which is a partial ordering), every set of pairwise incomparable (i.e. not comparable) strings is finite), thus there must be only finitely many such minimal elements. In other words, the set of such minimal elements must be a finite set, e.g. in decimal (base b = 10), this set has exactly 77 elements: {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}.

For bases 2 ≤ b ≤ 36, Athena problem is fully solved in bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24, and also solved in bases b = 11, 13, 16, 22, 30 if probable primes are allowed. For the unsolved bases b = 17, 19, 21, 23, 25, 26, 27, 28, 29, 31, 32, 34, 35, 36, Athena problem is solved (if probable primes are allowed) except 771 families of the form x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) = sequence {xz, xyz, xyyz, xyyyz, xyyyyz, xyyyyyz, ...} (i.e. "xy⁺z" in regular expression), all of these 771 families contain no primes > b or probable primes > b with length ≤ 100000.

To solve the Athena problem for a given base b, we must compute the elements up to families of the form x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b), and find the smallest prime > b in all such families.

We call families of the form x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) "linear" families, and we reduce these families by removing all trailing digits y from x, and removing all leading digits y from z, to make the families be easier, e.g. family 12333{3}33345 in base b is reduced to family 12{3}45 in base b, since they are in fact the same family. Our algorithm then proceeds as follows:

• 1. M := {minimal primes in base b of length 2 or 3}, L := union of all x{Y}z (where x and z are strings (may be empty) of digits in base b) such that x ≠ 0 and gcd(z, b) = 1 and Y is the set of digits y in base b such that xyz has no subsequence in M.
• 2. While L contains nonlinear families (families which are not linear families): Explore each family of L, and update L. Examine each family of L by:
• 2.1. Let w be the shortest string in the family. If w has a subsequence in M, then remove the family from L. If w represents a prime, then add w to M and remove the family from L.
• 2.2. If possible, simplify the family.
• 2.3. Using the techniques below (covering congruence, algebraic factorization, or combine of them), check if the family can be proven to only contain composites (only count the numbers > b), and if so then remove the family from L.
• 3. Update L, after each split examine the new families as in step 2.

e.g. in decimal (base b = 10):

M := {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}

L := {2{0,2}1, 2{0,8}7, 3{0,3,6,9}3, 3{0,3,6,9}9, 4{6}9, 5{0,5,8}1, 5{0,2}7, 6{0,3,6,9}3, 6{0,3,4,6,9}9, 7{0,7}7, 8{0,5}1, 8{0}7, 9{0,2,5,8}1, 9{0,3,6,9}3, 9{0,3,4,6,9}9}

and since 2221 is prime, it follows that the family 2{0,2}1 splits into the families 2{0}1 and 2{0}2{0}1

and since the family 2{0}1 can be proven to contain no primes > base (since all numbers in this family are divisible by 3), it can be removed

and since 20201 is prime, it follows that the family 2{0}2{0}1 splits into the families 2{0}21 and 22{0}1

221 and 2021 are composites, but 20021 is prime, thus add 20021 to L

none of 221, 2201, 22001, 220001, 2200001 are primes, but 22000001 is prime, thus add 22000001 to L

and since the family 3{0,3,6,9}3 can be proven to contain no primes > base (since all numbers in this family are divisible by 3), it can be removed

etc.

Since the number of possible (first digit,last digit) (also called (initial digit,final digit)) combos (ordered pairs) of a prime > b in base b is (b−1)×eulerphi(b) (all digits except 0 can be the first digit of a prime > b in base b (thus b−1 possible digits), but only the digits coprime to b can be the last digit of a prime > b in base b (thus eulerphi(b) possible digits), and by the rule of product, there are (b−1)×eulerphi(b) choices of the (first digit,last digit) combo, also, both "numbers of primes in the set of the Athena problem in base b" and "length of the largest prime in the set of the Athena problem in base b" are roughly e^{γ×(b−1)×eulerphi(*b*)}.

Shrinking the 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)

• If y ∈ Y and the string xyyz represents a prime > b in base b (in this case, add this prime to the list) or has a subsequence which represents a prime > b in base b, then x{Y}z can be replaced with x{Y \ y}z ∪ x{Y \ y}y{Y \ y}z.
• If y₁ ∈ Y and y₂ ∈ Y and y₁ ≠ y₂ and the string xy₁y₂z represents a prime > b in base b (in this case, add this prime to the list) or has a subsequence which represents a prime > b in base b, then x{Y}z can be replaced with x{Y \ y₁}{Y \ y₂}z.
• If y₁ ∈ Y and y₂ ∈ Y and y₁ ≠ y₂ and both the strings xy₁y₂z and xy₂y₁z represent a prime > b in base b (in this case, add this prime to the list) or have a subsequence which represents a prime > b in base b, then x{Y}z can be replaced with x{Y \ y₁}z ∪ x{Y \ y₂}z.

e.g. in decimal (base b = 10):

• 2221 is a prime > 10, thus the family 2{0,2}1 splits into the two families 2{0}1 and 2{0}2{0}1.
• 227 is a prime > 10, and it is a subsequence of 5227, thus the family 5{0,2}7 splits into the two families 5{0}7 and 5{0}2{0}7.
• 449 is a prime > 10, and it is a subsequence of 6449, thus the family 6{0,3,4,6,9}9 splits into the two families 6{0,3,6,9}9 and 6{0,3,6,9}4{0,3,6,9}9.
• Both 5051 and 5501 are primes > 10, thus the family 5{0,5}1 splits into the two families 5{0}1 and 5{5}1 = {5}1.
• 8501 is a prime > 10, thus the family 8{0,5}1 splits into the family 8{0}{5}1.
• 887 is a prime > 10, and it is a subsequence of 2887, also 2087 is a prime > 10, thus the family 2{0,8}7 splits into the two families 2{0}7 and 28{0}7.
• 349 and 449 are primes > 10, and they are subsequences of 9349 and 9449, respectively, also 9049, 9649, 9949 are primes > 10, thus the family 9{0,3,4,6,9}9 splits into the two families 9{0,3,6,9}9 and 94{0,3,6,9}9.
• 251, 281, 521, 821, 881 are primes > 10, and they are subsequences of 9251, 9281, 9521, 9821, 9881, respectively, also 9001, 9221, 9551, 9851 are primes > 10, thus the family 9{0,2,5,8}1 splits into the numbers {91, 901, 921, 951, 981, 9021, 9051, 9081, 9201, 9501, 9581, 9801, 90581, 95081, 95801}.

If the methods we have discussed cannot be used to rule out or shrink x{Y}z where Y = {y₁, y₂, ..., y_n}, then we can replace x{Y}z by xy₁{Y}z ∪ xy₂{Y}z ∪ ... ∪ xy_n{Y}z and re-run the methods on this new language.

If all remain families are linear families (i.e. of the form x{y}z, where x and z are strings (may be empty) of digits in base b, y is a digit in base b), then we search the smallest (probable) primes in these families and add these primes to the list.

e.g. in decimal (base b = 10):

• The smallest prime in the family 5{0}27 is 5000000000000000000000000000027.
• The smallest prime in the family {5}1 is 555555555551.
• The smallest prime in the family 8{5}1 is 8555555555555555555551, but 8555555555555555555551 is not a minimal element since 555555555551 is a subsequence of 8555555555555555555551.

There is no guarantee that the techniques discussed will ever terminate, but in practice they often do. They are able to determine the set of the minimal elements in base b for 2 ≤ b ≤ 16 and b = 18, 20, 22, 24, 30. The bases b = 17, 19, 21, 23, 25 ≤ b ≤ 29, 31 ≤ b ≤ 36 are solved with the exception of 771 families of the form x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b).

The following is a "semi-algorithm" that is guaranteed to solve the Athena problem for a given base b, but it is not so easy to implement:

1. M = ∅
2. while (L ≠ ∅) do
3. choose x, a shortest string in L
4. M := M ∪ {x}
5. L := L − sup({x})

In practice, for arbitrary L, we cannot feasibly carry out step 5. Instead, we work with L', some regular overapproximation to L, until we can show L' = ∅ (which implies L = ∅). In practice, L' is usually chosen to be a finite union of sets of the form L₁{L₂}L₃, where each of L₁, L₂, L₃ is finite. In the case we consider in this project, we then have to determine whether such a family contains a prime or not.

Thus, the time complexity of the Athena problem in base b may be O(e^{γ×(b−1)×eulerphi(*b*)}), and the CPU time of the Athena problem in base b may be longer than the age of the universe for bases b = 19, 23, 25, 27, 29, 31, 32, 33, 34, 35, also, Athena problem in bases b around 500 may be NP-complete or NP-hard, or an undecidable problem, or an example of Gödel's incompleteness theorems (like the continuum hypothesis and the halting problem).

To solve the Athena problem, 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 is recursively solvable (just like Sierpiński problem and Riesel problem, Sierpiński problem and Riesel problem can be generalized to other bases b (references: http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.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), in fact, Athena problem base b covers the Sierpiński problem base b and the Riesel problem base b with k < b, i.e. finding the smallest prime of the form k×bⁿ+1 and k×bⁿ−1 (or prove such prime does not exist) with k < b (specially, for bases b such that the conjectured smallest Sierpiński number or the conjectured smallest Riesel number is < b, Athena problem base b covers the Sierpiński problem base b or the Riesel problem base b, respectively), since the smallest prime of the form k×bⁿ+1 and k×bⁿ−1 (if exists) must be a minimal element in base b, also, Athena problem base b covers finding the smallest prime of these forms in base b (or proving that such prime does not exist): (bⁿ−1)/(b−1) (for this form, n must be prime, and we want n ≥ 2) (references of this form: http://www.fermatquotient.com/PrimSerien/GenRepu.txt, https://web.archive.org/web/20021111141203/http://www.users.globalnet.co.uk/~aads/primes.html, http://www.primenumbers.net/Henri/us/MersFermus.htm, http://www.bitman.name/math/table/379, https://oeis.org/A084740, https://oeis.org/A084738, https://oeis.org/A128164, https://oeis.org/A285642; or for prime bases b: https://oeis.org/A065854, https://oeis.org/A279068), bⁿ+1 (for this form, n must be power of 2, and we want n ≥ 1) (references of this form: http://jeppesn.dk/generalized-fermat.html, http://www.noprimeleftbehind.net/crus/GFN-primes.htm, https://web.archive.org/web/20231002190634/http://yves.gallot.pagesperso-orange.fr/primes/index.html, https://oeis.org/A079706, https://oeis.org/A084712, https://oeis.org/A228101), (bⁿ+1)/2 (for odd b) (for this form, n must be power of 2, and we want n ≥ 2) (reference of this form: http://www.fermatquotient.com/PrimSerien/GenFermOdd.txt), (sqrt(b)×bⁿ+1)/(sqrt(b)+1) (for square b) (for this form, 2×n+1 must be prime, and we want n ≥ 2) (references of this form: http://www.fermatquotient.com/PrimSerien/GenRepuP.txt, http://www.primenumbers.net/Henri/us/MersFermus.htm, http://www.bitman.name/math/table/488, https://oeis.org/A084742, https://oeis.org/A084741; or for bases b with sqrt(b) prime: https://oeis.org/A065507), ((b−2)×bⁿ+1)/(b−1) (n ≥ 2) (reference of this form: https://oeis.org/A243404), 2×bⁿ+1 (n ≥ 1) (references of this form: https://www.mersenneforum.org/showthread.php?t=6918, https://www.mersenneforum.org/showthread.php?t=19725, https://oeis.org/A119624), 2×bⁿ−1 (n ≥ 1) (references of this form: https://www.mersenneforum.org/showthread.php?t=24576, https://www.mersenneforum.org/attachment.php?attachmentid=20976&d=1567314217, https://oeis.org/A119591), bⁿ+2 (n ≥ 1) (references of this form: https://oeis.org/A138066, https://oeis.org/A084713, https://oeis.org/A138067), bⁿ−2 (n ≥ 2) (references of this form: https://www.primepuzzles.net/puzzles/puzz_887.htm, https://oeis.org/A250200, https://oeis.org/A255707, https://oeis.org/A084714; or for prime bases b: https://oeis.org/A292201), (b−1)×bⁿ+1 (n ≥ 1) (references of this form: https://harvey563.tripod.com/wills.txt, http://www.noprimeleftbehind.net/Williams-primes-MM.htm, http://www.bitman.name/math/table/484; or for prime bases b: https://oeis.org/A122396), (b−1)×bⁿ−1 (n ≥ 1) (references of this form: http://www.noprimeleftbehind.net/Williams-primes-MP.htm, http://www.bitman.name/math/table/477, https://oeis.org/A305531; or for prime bases b: https://oeis.org/A087139), bⁿ+(b−1) (n ≥ 1) (references of this form: http://www.bitman.name/math/table/795, https://oeis.org/A076845, https://oeis.org/A076846, https://oeis.org/A078178, https://oeis.org/A078179), bⁿ−(b−1) (n ≥ 2) (references of this form: http://www.bitman.name/math/table/792, https://oeis.org/A113516, https://oeis.org/A343589; or for prime bases b: https://cs.uwaterloo.ca/journals/JIS/VOL3/mccranie.html, http://www.bitman.name/math/table/435)):

Problem: Given strings x, z (may be empty), a digit y, and a base b (x does not start with the digit 0, z ends with a digit which coprime to b, y is not 0 if x is empty, y is coprime to b if z is empty), does there exist a prime number whose base-b expansion is of the form xy_nz for some n ≥ 0?

Some families can be ruled out to contain no prime > b by covering congruence, algebraic factorization (e.g. difference of two squares, sum of two cubes, Sophie Germain's identity of x⁴+4×y⁴), or combine of them, e.g.

• The base 9 family 2{7}: Always divisible by 2 or 5
• The base 16 family {8}F: Always divisible by 3, 7, or 13
• The base 21 family {7}D: Always divisible by 2, 13, or 17
• The base 23 family {D}GA: Always divisible by 2, 5, 7, 37, or 79
• The base 9 family 3{8}: Can be written as 4×9ⁿ−1 and can be factored as (2×3ⁿ−1) × (2×3ⁿ+1)
• The base 8 family 1{0}1: Can be written as 8ⁿ+1 and can be factored as (2ⁿ+1) × (4ⁿ−2ⁿ+1)
• The base 16 family {4}1: Can be written as (4×16ⁿ−49)/15 and can be factored as (2×3ⁿ−7) × (2×3ⁿ+7) / 15
• The base 16 family {C}D: Can be written as (4×16ⁿ+1)/5 and can be factored as (2×4ⁿ−2×2ⁿ+1) × (2×4ⁿ+2×2ⁿ+1) / 5
• The base 14 family 8{D}: Can be written as 9×14ⁿ−1, it is divisible by 5 if n is odd and can be factored as (3×14^n/2−1) × (3×14^n/2+1) if n is even
• The base 12 family {B}9B: Can be written as 12ⁿ−25, it is divisible by 13 if n is odd and can be factored as (12^n/2−5) × (12^n/2+5) if n is even
• The base 17 family 1{9}: Can be written as (25×17ⁿ−9)/16, it is divisible by 2 if n is odd and can be factored as (5×17^n/2−3) × (5×17^n/2+3) / 16 if n is even
• The base 19 family 1{6}: Can be written as (4×19ⁿ−1)/3, it is divisible by 5 if n is odd and can be factored as (2×19^n/2−1) × (2×19^n/2+1) / 3 if n is even

By the prime number theorem, the chance that a random n-digit base b number is prime is approximately 1/n (more accurately, the chance is approximately 1/(n×ln(b)), where ln is the natural logarithm). If one conjectures the numbers x{y}z behave similarly (i.e. the numbers x{y}z is a pseudorandom sequence) you would expect 1/1 + 1/2 + 1/3 + 1/4 + ... = ∞ primes of the form x{y}z (of course, this does not always happen, since some x{y}z families can be ruled out to contain no prime > b (by covering congruence, algebraic factorization, or combine of them), but it is at least a reasonable conjecture in the absence of evidence to the contrary. Hence, the heuristic argument suggests there are always infinitely many primes in family x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) if it cannot be ruled out to contain no prime or only contain finitely many primes, by covering congruence, algebraic factorization, or combine of them. However, some families x{y}z 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. e.g. the smallest (probable) prime in the family A{3}A in base b = 13 is A3₅₉₂₁₉₇A, its algebraic form is (41×13⁵⁹²¹⁹⁸+27)/4, when written in decimal contains 659677 digits (it is only probable prime, i.e. not definitely prime).

These are the results of the Athena problem in bases 2 ≤ b ≤ 36 (we stop at base 36 since this base is the maximum base for which it is possible to write the numbers with the symbols 0, 1, 2, ..., 9 and A, B, C, ..., Z (i.e. the 10 Arabic numerals and the 26 Latin letters): (some large primes are only probable primes, i.e. not definitely primes, since they are too large to be ECPP proved and neither N−1 nor N+1 can be ≥ 1/3 factored, all of them pass the Baillie–PSW primality test and the strong primality test (i.e. the Miller–Rabin primality test) with all prime bases p ≤ 61, however, all 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 are definitely primes, most of them > 10²⁹⁹ are proven primes with ECPP proving, others > 10²⁹⁹ are proven primes with N−1 or N+1 proving)

All numbers are written in base b, using A to Z to represent digit values 10 to 35, "{}" means repeating, e.g. family 12{3}45 means the sequence {1245, 12345, 123345, 1233345, 12333345, 123333345, ...} (where the members are expressed as base b strings), subscripts are used to indicate repetitions of digits, e.g. 123₄567 means 123333567 (all subscripts are written in decimal).

Base 2: 1 prime (the largest of which has 2 digits (it is 11, and its value is 3 in decimal)): {11}

Base 3: 3 primes (the largest of which has 3 digits (it is 111, and its value is 13 in decimal)): {12, 21, 111}

Base 4: 5 primes (the largest of which has 3 digits (it is 221, and its value is 41 in decimal)): {11, 13, 23, 31, 221}

Base 5: 22 primes (the largest of which has 96 digits (it is 10₉₃13, and its algebraic form is 5⁹⁵+8)): {12, 21, 23, 32, 34, 43, 104, 111, 131, 133, 313, 401, 414, 3101, 10103, 14444, 30301, 33001, 33331, 44441, 300031, 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013}

Base 6: 11 primes (the largest of which has 5 digits (it is 40041, and its value is 5209 in decimal)): {11, 15, 21, 25, 31, 35, 45, 51, 4401, 4441, 40041}

Base 7: 71 primes (the largest of which has 17 digits (it is 3₁₆1, and its algebraic form is (7¹⁷−5)/2)): {14, 16, 23, 25, 32, 41, 43, 52, 56, 61, 65, 113, 115, 131, 133, 155, 212, 221, 304, 313, 335, 344, 346, 364, 445, 515, 533, 535, 544, 551, 553, 1022, 1051, 1112, 1202, 1211, 1222, 2111, 3031, 3055, 3334, 3503, 3505, 3545, 4504, 4555, 5011, 5455, 5545, 5554, 6034, 6634, 11111, 11201, 30011, 30101, 31001, 31111, 33001, 33311, 35555, 40054, 100121, 150001, 300053, 351101, 531101, 1100021, 33333301, 5100000001, 33333333333333331}

Base 8: 75 primes (the largest of which has 221 digits (it is 4₂₂₀7, and its algebraic form is (4×8²²¹+17)/7)): {13, 15, 21, 23, 27, 35, 37, 45, 51, 53, 57, 65, 73, 75, 107, 111, 117, 141, 147, 161, 177, 225, 255, 301, 343, 361, 401, 407, 417, 431, 433, 463, 467, 471, 631, 643, 661, 667, 701, 711, 717, 747, 767, 3331, 3411, 4043, 4443, 4611, 5205, 6007, 6101, 6441, 6477, 6707, 6777, 7461, 7641, 47777, 60171, 60411, 60741, 444641, 500025, 505525, 3344441, 4444477, 5500525, 5550525, 55555025, 444444441, 744444441, 77774444441, 7777777777771, 555555555555525, 44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444447}

Base 9: 151 primes (the largest of which has 1161 digits (it is 30₁₁₅₈11, and its algebraic form is 3×9¹¹⁶⁰+10)): {12, 14, 18, 21, 25, 32, 34, 41, 45, 47, 52, 58, 65, 67, 74, 78, 81, 87, 117, 131, 135, 151, 155, 175, 177, 238, 272, 308, 315, 331, 337, 355, 371, 375, 377, 438, 504, 515, 517, 531, 537, 557, 564, 601, 638, 661, 702, 711, 722, 735, 737, 751, 755, 757, 771, 805, 838, 1011, 1015, 1101, 1701, 2027, 2207, 3017, 3057, 3101, 3501, 3561, 3611, 3688, 3868, 5035, 5051, 5071, 5101, 5501, 5554, 5705, 5707, 7017, 7075, 7105, 7301, 8535, 8544, 8555, 8854, 20777, 22227, 22777, 30161, 33388, 50161, 50611, 53335, 55111, 55535, 55551, 57061, 57775, 70631, 71007, 77207, 100037, 100071, 100761, 105007, 270707, 301111, 305111, 333035, 333385, 333835, 338885, 350007, 500075, 530005, 555611, 631111, 720707, 2770007, 3030335, 7776662, 30300005, 30333335, 38333335, 51116111, 70000361, 300030005, 300033305, 351111111, 1300000007, 5161111111, 8333333335, 300000000035, 311111111161, 544444444444, 2000000000007, 5700000000001, 7270000000007, 88888888833335, 100000000000507, 5111111111111161, 7277777777777777707, 8888888888888888888335, 30000000000000000000051, 1000000000000000000000000057, 56111111111111111111111111111111111111, 7666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666662, 27777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777707, 300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011}

Base 10: 77 primes (the largest of which has 31 digits (it is 50₂₈27, and its algebraic form is 5×10³⁰+27)): {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}

Base 11: 1068 primes (including 1 unproven probable prime: 57₆₂₆₆₈), the largest of which has 62669 digits (it is 57₆₂₆₆₈, and its algebraic form is (57×11⁶²⁶⁶⁸−7)/10), see Data of Athena problem base 11

Base 12: 106 primes (the largest of which has 42 digits (it is 40₃₉77, and its algebraic form is 4×12⁴¹+91)): {11, 15, 17, 1B, 25, 27, 31, 35, 37, 3B, 45, 4B, 51, 57, 5B, 61, 67, 6B, 75, 81, 85, 87, 8B, 91, 95, A7, AB, B5, B7, 221, 241, 2A1, 2B1, 2BB, 401, 421, 447, 471, 497, 565, 655, 665, 701, 70B, 721, 747, 771, 77B, 797, 7A1, 7BB, 907, 90B, 9BB, A41, B21, B2B, 2001, 200B, 202B, 222B, 229B, 292B, 299B, 4441, 4707, 4777, 6A05, 6AA5, 729B, 7441, 7B41, 929B, 9777, 992B, 9947, 997B, 9997, A0A1, A201, A605, A6A5, AA65, B001, B0B1, BB01, BB41, 600A5, 7999B, 9999B, AAAA1, B04A1, B0B9B, BAA01, BAAA1, BB09B, BBBB1, 44AAA1, A00065, BBBAA1, AAA0001, B00099B, AA000001, BBBBBB99B, B0000000000000000000000000009B, 400000000000000000000000000000000000000077}

Base 13: 3197 primes (including 4 unproven probable primes: C5₂₃₇₅₅C, 80₃₂₀₁₇111, 95₁₉₇₄₂₀, A3₅₉₂₁₉₇A), the largest of which has 592199 digits (it is A3₅₉₂₁₉₇A, and its algebraic form is (41×13⁵⁹²¹⁹⁸+27)/4), see Data of Athena problem base 13

Base 14: 650 primes, the largest of which has 19699 digits (it is 4D₁₉₆₉₈, and its algebraic form is 5×14¹⁹⁶⁹⁸−1), see Data of Athena problem base 14

Base 15: 1284 primes, the largest of which has 157 digits (it is 7₁₅₅97, and its algebraic form is (15¹⁵⁷+59)/2), see Data of Athena problem base 15

Base 16: 2347 primes (including 3 unproven probable primes: DB₃₂₂₃₄, 4₇₂₇₈₅DD, 3₁₁₆₁₃₇AF), the largest of which has 116139 digits (it is 3₁₁₆₁₃₇AF, and its algebraic form is (16¹¹⁶¹³⁹+619)/5), see Data of Athena problem base 16

Base 17: 10415 known primes (including many unproven probable primes) and 12 unsolved families (1{7}, 1F{0}7, 4{7}A, 70F{0}D, 8{B}9, 9{5}9, A{D}F, B{0}B3, {B}E9, {B}EE, F1{9}, FD0{D}, no primes or probable primes with length ≤ 200000, nor can be proven to only contain composites), see Data of Athena problem base 17

Base 18: 549 primes, the largest of which has 6271 digits (it is C0₆₂₆₈C5, and its algebraic form is 12×18⁶²⁷⁰+221), see Data of Athena problem base 18

Base 19: 31417 known primes (including many unproven probable primes) and 17 unsolved families (4B5{0}H, {5}3, 5{H}05, 5{H}0H, 5{H}5, 66{B}, 71{0}177, 7AF{0}H, 97{0}3, C{H}C, EE1{6}, F{7}5, F{B}G, F{D}F, H0F{0}7A, HB{0}5B5, II{D}, no primes or probable primes with length ≤ 200000, nor can be proven to only contain composites), see Data of Athena problem base 19

Base 20: 3314 primes, the largest of which has 6271 digits (it is G0₆₂₆₉D, and its algebraic form is 16×20⁶²⁷⁰+13), see Data of Athena problem base 20

Base 21: 13386 known primes (including many unproven probable primes) and 8 unsolved families (5{0}DJ, {9}D, B3{0}EB, B{H}6H, C{F}0K, {F}35, G{0}FK, H{0}7771, no primes or probable primes with length ≤ 200000, nor can be proven to only contain composites), see Data of Athena problem base 21

Base 22: 8003 primes (including 1 unproven probable prime: BK₂₂₀₀₁5), the largest of which has 22003 digits (it is BK₂₂₀₀₁5, and its algebraic form is (251×22²²⁰⁰²−335)/21), see Data of Athena problem base 22

Base 23: 65178 known primes (including many unproven probable primes) and 87 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 23 and Data of unsolved families for base 23

Base 24: 3409 primes, the largest of which has 8134 digits (it is N00N₈₁₂₉LN, and its algebraic form is 13249×24⁸¹³¹−49), see Data of Athena problem base 24

Base 25: 133639 known primes (including many unproven probable primes) and 85 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 25 and Data of unsolved families for base 25

Base 26: 25256 known primes (including 7 unproven probable primes: 5₁₉₃₉₁6F, 7₂₀₂₇₉OL, LD0₂₀₉₇₅7, 6K₂₃₃₀₀5, J0₄₄₃₀₃KCB, M0₆₁₁₈₆2BB, 85M₁₉₇₀₆₀B) and 3 unsolved families ({A}6F, {H}MH, {I}GL, no primes or probable primes with length ≤ 200000, nor can be proven to only contain composites), see Data of Athena problem base 26

Base 27: 102852 known primes (including many unproven probable primes) and 44 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 27 and Data of unsolved families for base 27

Base 28: 25528 known primes (including 3 unproven probable primes: N6₂₄₀₅₁LR, 5OA₃₁₂₃₈F, O4O₉₄₅₃₅9) and 1 unsolved family (O{A}F, no primes or probable primes with length ≤ 900000, nor can be proven to only contain composites), see Data of Athena problem base 28

Base 29: 355242 known primes (including many unproven probable primes) and 125 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 29 and Data of unsolved families for base 29

Base 30: 2619 primes (including 1 unproven probable prime: I0₂₄₆₀₈D), the largest of which has 34206 digits (it is OT₃₄₂₀₅, and its algebraic form is 25×30³⁴²⁰⁵−1), see Data of Athena problem base 30

Base 31: 569323 known primes (including many unproven probable primes) and 77 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 31 and Data of unsolved families for base 31

Base 32: 168882 known primes (including many unproven probable primes) and 120 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 32 and Data of unsolved families for base 32

Base 33: 280012 known primes (including many unproven probable primes) and 81 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 33 and Data of unsolved families for base 33

Base 34: 184785 known primes (including many unproven probable primes) and 47 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 34 and Data of unsolved families for base 34

Base 35: 720002 known primes (including many unproven probable primes) and 60 unsolved families (no primes or probable primes with length ≤ 100000, nor can be proven to only contain composites), see Data of Athena problem base 35 and Data of unsolved families for base 35

Base 36: 35286 known primes (including 3 unproven probable primes: 7K₂₆₅₆₇Z, S0₇₅₀₀₇8H, P₈₁₉₉₃SZ) and 4 unsolved families (B{0}EUV, HM{0}N, N{0}YYN, O{L}Z, no primes or probable primes with length ≤ 200000, nor can be proven to only contain composites), see Data of Athena problem base 36

Bold for the minimal elements, x ◁ y means x is a subsequence of y.

Assume p is a prime > 10, and the last digit of p must lie in {1,3,7,9}.

Case 1: p ends with 1.

In this case we can write p = x1. If x contains 1, 3, 4, 6, or 7, then (respectively) 11 ◁ p, 31 ◁ p, 41 ◁ p, 61 ◁ p, or 71 ◁ p. Hence we may assume all digits of x are 0, 2, 5, 8, or 9.

Case 1.1: p begins with 2.

In this case we can write p = 2y1. If 5 ◁ y, then 251 ◁ p. If 8 ◁ y, then 281 ◁ p. If 9 ◁ y, then 29 ◁ p. Hence we may assume all digits of y are 0 or 2.

If 22 ◁ y, then 2221 ◁ p. Hence we may assume y contains zero or one 2's.

If y contains no 2's, then p ∈ 2{0}1. But then, since the sum of the digits of p is 3, p is divisible by 3, so p cannot be prime.

If y contains exactly one 2, then we can write p = 2z2w1, where z,w ∈ {0}. If 0 ◁ z and 0 ◁ w, then 20201 ◁ p. Hence we may assume either z or w is empty.

If z is empty, then p ∈ 22{0}1, and the smallest prime p ∈ 22{0}1 is 22000001.

If w is empty, then p ∈ 2{0}21, and the smallest prime p ∈ 2{0}21 is 20021.

Case 1.2: p begins with 5.

In this case we can write p = 5y1. If 2 ◁ y, then 521 ◁ p. If 9 ◁ y, then 59 ◁ p. Hence we may assume all digits of y are 0, 5, or 8.

If 05 ◁ y, then 5051 ◁ p. If 08 ◁ y, then 5081 ◁ p. If 50 ◁ y, then 5501 ◁ p. If 58 ◁ y, then 5581 ◁ p. If 80 ◁ y, then 5801 ◁ p. If 85 ◁ y, then 5851 ◁ p. Hence we may assume y ∈ {0} ∪ {5} ∪ {8}.

If y ∈ {0}, then p ∈ 5{0}1. But then, since the sum of the digits of p is 6, p is divisible by 3, so p cannot be prime.

If y ∈ {5}, then p ∈ 5{5}1, and the smallest prime p ∈ 5{5}1 is 555555555551.

If y ∈ {8}, since if 88 ◁ y, then 881 ◁ p, hence we may assume y ∈ {𝜆,8}, and thus p ∈ {51,581}, but 51 and 581 are both composite.

Case 1.3: p begins with 8.

In this case we can write p = 8y1. If 2 ◁ y, then 821 ◁ p. If 8 ◁ y, then 881 ◁ p. If 9 ◁ y, then 89 ◁ p. Hence we may assume all digits of y are 0 or 5.

If 50 ◁ y, then 8501 ◁ p. Hence we may assume y ∈ {0}{5}.

If 005 ◁ y, then 80051 ◁ p. Hence we may assume y ∈ {0} ∪ {5} ∪ 0{5}.

If y ∈ {0}, then p ∈ 8{0}1. But then, since the sum of the digits of p is 9, p is divisible by 3, so p cannot be prime.

If y ∈ {5}, since if 55555555555 ◁ y, then 555555555551 ◁ p, hence we may assume y ∈ {𝜆, 5, 55, 555, 5555, 55555, 555555, 5555555, 55555555, 555555555, 5555555555}, and thus p ∈ {81, 851, 8551, 85551, 855551, 8555551, 85555551, 855555551, 8555555551, 85555555551, 855555555551}, but all of these numbers are composite.

If y ∈ 0{5}, since if 55555555555 ◁ y, then 555555555551 ◁ p, hence we may assume y ∈ {0, 05, 055, 0555, 05555, 055555, 0555555, 05555555, 055555555, 0555555555, 05555555555}, and thus p ∈ {801, 8051, 80551, 805551, 8055551, 80555551, 805555551, 8055555551, 80555555551, 805555555551, 8055555555551}, and of these numbers only 80555551 and 8055555551 are primes, but 80555551 ◁ 8055555551, thus only 80555551 is a minimal element.

Case 1.4: p begins with 9.

In this case we can write p = 9y1. If 9 ◁ y, then 991 ◁ p. Hence we may assume all digits of y are 0, 2, 5, or 8.

If 00 ◁ y, then 9001 ◁ p. If 22 ◁ y, then 9221 ◁ p. If 55 ◁ y, then 9551 ◁ p. If 88 ◁ y, then 881 ◁ p. Hence we may assume y contains at most one 0, at most one 2, at most one 5, and at most one 8.

If y only contains at most one 0 and does not contain any of {2,5,8}, then y ∈ {𝜆,0}, and thus p ∈ {91,901}, but 91 and 901 are both composite. If y only contains at most one 0 and only one of {2,5,8}, then the sum of the digits of p is divisible by 3, p is divisible by 3, so p cannot be prime. Hence we may assume y contains at least two of {2,5,8}.

If 25 ◁ y, then 251 ◁ p. If 28 ◁ y, then 281 ◁ p. If 52 ◁ y, then 521 ◁ p. If 82 ◁ y, then 821 ◁ p. Hence we may assume y contains no 2's (since if y contains 2, then y cannot contain either 5's or 8's, which is a contradiction).

If 85 ◁ y, then 9851 ◁ p. Hence we may assume y ∈ {58,580,508,058}, and thus p ∈ {9581,95801,95081,90581}, and of these numbers only 95801 is prime, but 95801 is not a minimal element since 5801 ◁ 95801.

Case 2: p ends with 3.

In this case we can write p = x3. If x contains 1, 2, 4, 5, 7, or 8, then (respectively) 13 ◁ p, 23 ◁ p, 43 ◁ p, 53 ◁ p, 73 ◁ p, or 83 ◁ p. Hence we may assume all digits of x are 0, 3, 6, or 9, and thus all digits of p are 0, 3, 6, or 9. But then, since the digits of p all have a common factor 3, p is divisible by 3, so p cannot be prime.

Case 3: p ends with 7.

In this case we can write p = x7. If x contains 1, 3, 4, 6, or 9, then (respectively) 17 ◁ p, 37 ◁ p, 47 ◁ p, 67 ◁ p, or 97 ◁ p. Hence we may assume all digits of x are 0, 2, 5, 7, or 8.

Case 3.1: p begins with 2.

In this case we can write p = 2y7. If 2 ◁ y, then 227 ◁ p. If 5 ◁ y, then 257 ◁ p. If 7 ◁ y, then 277 ◁ p. Hence we may assume all digits of y are 0 or 8.

If 08 ◁ y, then 2087 ◁ p. If 88 ◁ y, then 887 ◁ p. Hence we may assume y ∈ {0} ∪ 8{0}.

If y ∈ {0}, then p ∈ 2{0}7. But then, since the sum of the digits of p is 9, p is divisible by 3, so p cannot be prime.

If y ∈ 8{0}, then p ∈ 28{0}7. But then p is divisible by 7, since for n ≥ 0 we have 7 × 40_n1 = 280_n7.

Case 3.2: p begins with 5.

In this case we can write p = 5y7. If 5 ◁ y, then 557 ◁ p. If 7 ◁ y, then 577 ◁ p. If 8 ◁ y, then 587 ◁ p. Hence we may assume all digits of y are 0 or 2.

If 22 ◁ y, then 227 ◁ p. Hence we may assume y contains zero or one 2's.

If y contains no 2's, then p ∈ 5{0}7. But then, since the sum of the digits of p is 12, p is divisible by 3, so p cannot be prime.

If y contains exactly one 2, then we can write p = 5z2w7, where z,w ∈ {0}. If 0 ◁ z and 0 ◁ w, then 50207 ◁ p. Hence we may assume either z or w is empty.

If z is empty, then p ∈ 52{0}7, and the smallest prime p ∈ 52{0}7 is 5200007.

If w is empty, then p ∈ 5{0}27, and the smallest prime p ∈ 5{0}27 is 5000000000000000000000000000027.

Case 3.3: p begins with 7.

In this case we can write p = 7y7. If 2 ◁ y, then 727 ◁ p. If 5 ◁ y, then 757 ◁ p. If 8 ◁ y, then 787 ◁ p. Hence we may assume all digits of y are 0 or 7, and thus all digits of p are 0 or 7. But then, since the digits of p all have a common factor 7, p is divisible by 7, so p cannot be prime.

Case 3.4: p begins with 8.

In this case we can write p = 8y7. If 2 ◁ y, then 827 ◁ p. If 5 ◁ y, then 857 ◁ p. If 7 ◁ y, then 877 ◁ p. If 8 ◁ y, then 887 ◁ p. Hence we may assume y ∈ {0}, and thus p ∈ 8{0}7. But then, since the sum of the digits of p is 15, p is divisible by 3, so p cannot be prime.

Case 4: p ends with 9.

In this case we can write p = x9. If x contains 1, 2, 5, 7, or 8, then (respectively) 19 ◁ p, 29 ◁ p, 59 ◁ p, 79 ◁ p, or 89 ◁ p. Hence we may assume all digits of x are 0, 3, 4, 6, or 9.

If 44 ◁ x, then 449 ◁ p. Hence we may assume x contains zero or one 4's.

If x contains no 4's, then all digits of x are 0, 3, 6, or 9, and thus all digits of p are 0, 3, 6, or 9. But then, since the digits of p all have a common factor 3, p is divisible by 3, so p cannot be prime. Hence we may assume that x contains exactly one 4.

Case 4.1: p begins with 3.

In this case we can write p = 3y4z9, where all digits of y, z are 0, 3, 6, or 9. We must have 349 ◁ p.

Case 4.2: p begins with 4.

In this case we can write p = 4y9, where all digits of y are 0, 3, 6, or 9. If 0 ◁ y, then 409 ◁ p. If 3 ◁ y, then 43 ◁ p. If 9 ◁ y, then 499 ◁ p. Hence we may assume y ∈ {6}, and thus p ∈ 4{6}9. But then p is divisible by 7, since for n ≥ 0 we have 7 × 6_n7 = 46_n9.

Case 4.3: p begins with 6.

In this case we can write p = 6y4z9, where all digits of y, z are 0, 3, 6, or 9. If 0 ◁ z, then 409 ◁ p. If 3 ◁ z, then 43 ◁ p. If 6 ◁ z, then 6469 ◁ p. If 9 ◁ z, then 499 ◁ p. Hence we may assume z is empty.

If 3 ◁ y, then 349 ◁ p. If 9 ◁ y, then 6949 ◁ p. Hence we may assume all digits of y are 0 or 6.

If 06 ◁ y, then 60649 ◁ p. Hence we may assume y ∈ {6}{0}.

If 666 ◁ y, then 666649 ◁ p. If 00000 ◁ y, then 60000049 ◁ p. Hence we may assume y ∈ {𝜆, 0, 00, 000, 0000, 6, 60, 600, 6000, 60000, 66, 660, 6600, 66000, 660000}, and thus p ∈ {649, 6049, 60049, 600049, 6000049, 6649, 66049, 660049, 6600049, 66000049, 66649, 666049, 6660049, 66600049, 666000049}, and of these numbers only 66000049 and 66600049 are primes.

Case 4.4: p begins with 9.

In this case we can write p = 9y4z9, where all digits of y, z are 0, 3, 6, or 9. If 0 ◁ y, then 9049 ◁ p. If 3 ◁ y, then 349 ◁ p. If 6 ◁ y, then 9649 ◁ p. If 9 ◁ y, then 9949 ◁ p. Hence we may assume y is empty.

If 0 ◁ z, then 409 ◁ p. If 3 ◁ z, then 43 ◁ p. If 9 ◁ z, then 499 ◁ p. Hence we may assume z ∈ {6}, and thus p ∈ 94{6}9, and the smallest prime p ∈ 94{6}9 is 946669.