Jump to content

Athena problem

Add links
From Wikiversity

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, write all prime numbers > b in the positional notation with base b (the digits are 0, 1, 2, ..., b−1), and regard them as strings (with alphabet Σb = {0, 1, 2, ..., b−1}), and find the set of the minimal elements of the set of these strings under the subsequence ordering.

By Higman's lemma, there are no infinite antichains for the subsequence ordering (i.e. the subsequence ordering is always a well quasi order), 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{d}y (where x and y are strings with alphabet Σb = {0, 1, 2, ..., b−1}, d is a base-b digit (i.e. an element in {0, 1, 2, ..., b−1}).

Results

[edit | edit source]

These are the results of the Athena problem in bases 2 ≤ b ≤ 36: (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)

To solve the Athena problem for a given base b, we must compute the elememt up to families of the form x{d}y (where x and y are strings with alphabet Σb = {0, 1, 2, ..., b−1}, d is a base-b digit (i.e. an element in {0, 1, 2, ..., b−1}), and find the smallest prime > b in all such families. 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 x4+4×y4), 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×9n−1 and can be factored as (2×3n−1) × (2×3n+1)
  • The base 8 family 1{0}1: Can be written as 8n+1 and can be factored as (2n+1) × (4n−2n+1)
  • The base 16 family {4}1: Can be written as (4×16n−49)/15 and can be factored as (2×3n−7) × (2×3n+7) / 15
  • The base 16 family {C}D: Can be written as (4×16n+1)/5 and can be factored as (2×4n−2×2n+1) × (2×4n+2×2n+1) / 5
  • The base 14 family 8{D}: Can be written as 9×14n−1, it is divisible by 5 if n is odd and can be factored as (3×14n/2−1) × (3×14n/2+1) if n is even
  • The base 12 family {B}9B: Can be written as 12n−25, it is divisible by 13 if n is odd and can be factored as (12n/2−5) × (12n/2+5) if n is even
  • The base 17 family 1{9}: Can be written as (25×17n−9)/16, it is divisible by 2 if n is odd and can be factored as (5×17n/2−3) × (5×17n/2+3) / 16 if n is even
  • The base 19 family 1{6}: Can be written as (4×19n−1)/3, it is divisible by 5 if n is odd and can be factored as (2×19n/2−1) × (2×19n/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{d}y behave similarly (i.e. the numbers x{d}y is a pseudorandom sequence) you would expect 1/1 + 1/2 + 1/3 + 1/4 + ... = ∞ primes of the form x{d}y (of course, this does not always happen, since some x{d}y 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{d}y (where x and y are strings with alphabet Σb = {0, 1, 2, ..., b−1}, d is a base-b digit (i.e. an element in {0, 1, 2, ..., b−1}) 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{d}y 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, e.g. the smallest (probable) prime in the family A{3}A in base b = 13 is A3592197A, which written in decimal contains 659677 digits (it is only probable prime, i.e. not definitely prime).

All numbers are written in 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. 1234567 means 123333567 (all subscripts are written in decimal).

Base 2: 1 prime (the largest of which has 2 digits): {11}

Base 3: 3 primes (the largest of which has 3 digits): {12, 21, 111}

Base 4: 5 primes (the largest of which has 3 digits): {11, 13, 23, 31, 221}

Base 5: 22 primes (the largest of which has 96 digits): {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): {11, 15, 21, 25, 31, 35, 45, 51, 4401, 4441, 40041}

Base 7: 71 primes (the largest of which has 17 digits): {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): {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): {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): {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: 5762668), see Data of Athena problem base 11

Base 12: 106 primes (the largest of which has 42 digits): {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: C523755C, 8032017111, 95197420, A3592197A), see Data of Athena problem base 13

Base 14: 650 primes, the largest of which has 19699 digits, see Data of Athena problem base 14

Base 15: 1284 primes, the largest of which has 157 digits, see Data of Athena problem base 15

Base 16: 2347 primes (including 3 unproven probable primes: DB32234, 472785DD, 3116137AF), 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 and Data of unsolved families for base 17

Base 18: 549 primes, the largest of which has 6271 digits, 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 and Data of unsolved families for base 19

Base 20: 3314 primes, the largest of which has 6271 digits, 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 and Data of unsolved families for base 21

Base 22: 8003 primes (including 1 unproven probable prime: BK220015), 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, 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: 5193916F, 720279OL, LD0209757, 6K233005, J044303KCB, M0611862BB, 85M197060B) 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: N624051LR, 5OA31238F, O4O945359) and 1 unsolved family (O{A}F, no primes or probable primes with length ≤ 709070, 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: I024608D), 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: 7K26567Z, S0750078H, P81993SZ) 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

Retrieved from "https://en.wikiversity.org/w/index.php?title=Athena_problem&oldid=2808986"