Problem 83. Follow-up to Puzzle 178

Richard Chen sent the following nice follow-up to puzzle 178, as his added condition to the original Shallit approach:

Puzzle 178 is finding the minimal set of S for a given set S, such as S = {prime = 1 mod 4}, {prime = 3 mod 4}, {palindromic prime}, etc.

A string a is a subsequence of another string b, if a can be obtained from b by deleting zero or more of the characters in b. For example, 514 is a substring of 251664. The empty string is a subsequence of every string.
Two strings a and b are comparable if either a is a substring of b, or b is a substring of a.
A surprising result from formal language theory is that every set of pairwise incomparable strings is finite. This means that from any set of strings we can find its minimal elements.
A string a in a set of strings S is minimal if whenever b (an element of S) is a substring of a, we have b = a.
This set must be finite!

For example, if our set is the set of prime numbers (written in radix 10), then we get the set {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}, and if our set is the set of composite numbers (written in radix 10), then we get the set {4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70, 72, 75, 77, 111, 117, 171, 371, 711, 713, 731}

Besides, if our set is the set of prime numbers written in radix b, then we get these sets:

b, we get the set

2: {10, 11}

3: {2, 10, 111}

4: {2, 3, 11}

5: {2, 3, 10, 111, 401, 414, 14444, 44441}

6: {2, 3, 5, 11, 4401, 4441, 40041}

these are already researched in https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf.

Now, let's consider: if our set is the set of prime numbers > b written in radix b, then we get the sets:

(using A−Z to represent digit values 10 to 35)

b: the set for base b

2: {11}

3: {12, 21, 111}

4: {11, 13, 23, 31, 221}

5: {12, 21, 23, 32, 34, 43, 104, 111, 131, 133, 313, 401, 414, 3101, 10103, 14444, 30301, 33001, 33331, 44441, 300031,
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013}

6: {11, 15, 21, 25, 31, 35, 45, 51, 4401, 4441, 40041}

8: {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, 44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444
44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444
4444444444447}

10: {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}

12: {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}

I have only solved these base, i.e. I have found all such primes (elements in the minimal set of the primes >b in base b) and proved that these are all such primes.

For other bases up to 16, I only found all such primes up to certain limit and some larger such primes, e.g. for base 7, I only searched to the prime 5100000001, and the current set is

{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, ...}

I cannot prove that this set is complete.

Also for base 9, I only searched to the prime 8333333335, and the current set is

{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,
..., 5111111111111161, ..., 30000000000000000000051, ..., 56111111111111111111111111111111111111, ...,
766666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666662, ..., 30000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000011, ...}

And for base 11, I only searched to the prime 1500000001, and the current set is

{12, 16, 18, 21, 27, 29, 34, 38, 3A, 43, 49, 54, 56, 61, 65, 67, 72, 76, 81, 89, 92, 94, 98, 9A, A3, 10A, 115, 117, 133, 139, 153,
155, 171, 193, 197, 199, 1AA, 225, 232, 236, 25A, 263, 315, 319, 331, 335, 351, 353, 362, 373, 379, 391, 395, 407, 414, 452,
458, 478, 47A, 485, 4A5, 4A7, 502, 508, 511, 513, 533, 535, 539, 551, 571, 579, 588, 595, 623, 632, 70A, 711, 715, 731, 733,
737, 755, 759, 775, 791, 797, 7AA, 803, 847, 858, 85A, 874, 885, 887, 913, 919, 931, 937, 957, 959, 975, 995, A07, A1A, A25,
A45, A74, A7A, A85, AA1, AA7, 1101, 11A9, 1305, 1451, 1457, 15A7, 175A, 17A5, 17A9, 2023, 2045, 2052, 2083, 20A5,
2333, 2A05, 2A52, 3013, 3026, 3059, 3097, 3206, 3222, 3233, 3307, 3332, 3505, 4025, 4151, 4157, 4175, 4405, 4445, 4487,
450A, 4575, 5017, 5031, 5059, 5075, 5097, 5099, 5105, 515A, 517A, 520A, 5301, 5583, 5705, 577A, 5853, 5873, 5909, 5A17,
5A57, 5A77, 5A8A, 6683, 66A9, 7019, 7073, 7079, 7088, 7093, 7095, 7309, 7451, 7501, 7507, 7578, 757A, 75A7, 7787, 7804,
7844, 7848, 7853, 7877, 78A4, 7A04, 7A57, 7A79, 7A95, 8078, 8245, 8333, 8355, 8366, 8375, 8425, 8553, 8663, 8708, 8777,
878A, 8A05, 9053, 9101, 9107, 9305, 9505, 9703, A052, A119, A151, A175, A515, A517, A575, A577, A5A8, A719, A779, A911,
AAA9, 10011, 10075, 10091, 10109, 10411, 10444, 10705, 10709, 10774, 10901, 11104, 11131, 11144, 11191, 1141A, 114A1,
13757, 1411A, 14477, 144A4, 14A04, 14A11, 17045, 17704, 1774A, 17777, 177A4, 17A47, 1A091, 1A109, 1A114, 1A404,
1A411, 1A709, 20005, 20555, 22203, 25228, 25282, 25552, 25822, 28522, 30037, 30701, 30707, 31113, 33777, 35009, 35757,
39997, 40045, 4041A, 40441, 4045A, 404A1, 4111A, 411A1, 42005, 44401, 44474, 444A1, 44555, 44577, 445AA, 44744,
44A01, 47471, 47477, 47701, 5057A, 50903, 5228A, 52A22, 52A55, 52A82, 55007, 550A9, 55205, 55522, 55557, 55593,
55805, 57007, 57573, 57773, 57807, 5822A, 58307, 58505, 58A22, 59773, 59917, 59973, 59977, 59999, 5A015, 5A2A2,
5AA99, 60836, 60863, 68636, 6A609, 6A669, 6A696, 6A906, 6A966, 70048, 70103, 70471, 70583, 70714, 71474, 717A4,
71A09, 74084, 74444, 74448, 74477, 744A8, 74747, 74774, 7488A, 74A48, 75773, 77144, 77401, 77447, 77799, 77A09,
78008, 78783, 7884A, 78888, 788A8, 79939, 79993, 79999, 7A051, 7A444, 7A471, 80005, 80252, 80405, 80522, 80757,
80AA5, 83002, 84045, 85307, 86883, 88863, 8A788, 90073, 90707, 90901, 95003, 97779, 97939, 99111, 99177, 99973,
A0111, A0669, A0966, A0999, A0A09, A1404, A4177, A4401, A4717, A5228, A52AA, A5558, A580A, A5822, A58AA,
A5A59, A5AA2, A6096, A6966, A6999, A7051, A7778, A7808, A9055, A9091, A9699, A9969, AA52A, AA58A, 100019,
100079, 101113, 101119, 101911, 107003, 140004, 144011, 144404, 1A0019, 1A0141, 1A5001, 1A7005, 1A9001, 222223,
222823, 300107, 300202, 300323, 303203, 307577, 310007, 332003, 370777, 400555, 401A11, 404001, 404111, 405AAA,
41A011, 440A41, 441011, 451777, 455555, 470051, 470444, 474404, 4A0401, 4A4041, 500015, 500053, 500077, 500507,
505577, 522A2A, 525223, 528A2A, 531707, 550777, 553707, 5555A9, 555A99, 557707, 55A559, 5807A7, 580A0A,
580A55, 58A0AA, 590007, 599907, 5A2228, 5A2822, 5A2AAA, 5A552A, 5AA22A, 5AAA22, 60A069, 683006, 6A0096,
6A0A96, 6A9099, 6A9909, 700778, 701074, 701777, 704408, 704417, 704457, 704484, 707041, 707441, 707708, 707744,
707784, 710777, 717044, 717077, 740008, 74484A, 770441, 770744, 770748, 770771, 777017, 777071, 777448, 777484,
777701, 7778A8, 777A19, 777A48, 778883, 78A808, 790003, 7A1009, 7A4408, 7A7708, 80A555, 828283, 828883,
840555, 850505, 868306, 873005, 883202, 900701, 909739, 909979, 909991, 970771, 977701, 979909, 990739, 990777,
990793, 997099, 999709, 999901, A00009, A00599, A01901, A05509, A0A058, A0A955, A10114, A555A2, A55999,
A59991, A5A222, A5A22A, A60609, A66069, A66906, A69006, A79005, A87888, A90099, A90996, A96006, A96666,
A97177, A97771, AA0A58, AA5A22, AAA522, 1000501, 1011141, 1030007, 1070047, 111114A, 1111A14, 1111A41,
1144441, 14A4444, 1700005, 1700474, 1A44444, 2555505, 2845055, 3030023, 3100003, 3333397, 4000111, 4011111,
41A1111, 4411111, 444441A, 4444771, 4470004, 4505005, 4744417, 4774441, 4777404, 4777417, 4777747, 4A11111,
4A40001, 5000093, 50005A7, 5005777, 5050553, 5055503, 5070777, 5222222, 5222AAA, 52AAAA2, 52AAAAA, 5505053,
5552AAA, 5555599, 5555A58, 5558A0A, 5558A55, 5558AAA, 55A0009, 55AAA52, 580000A, 5822222, 58AAAAA,
5A2222A, 5AA2222, 6000A69, 6000A96, 6A00069, 7000417, 7000741, 7000835, 7000857, 7007177, 7008305, 7014447,
7017444, 7074177, 7077477, 7077741, 7077747, 7100447, 7174404, 717444A, 7400404, 7700717, 7701077, 7701707,
7707778, 7774004, 7777104, 777741A, 7777441, 777774A, 7777A47, 7779003, 777A008, 777A778, 777A808, 77A4777,
7900399, 8305007, 8500707, 8555707, 8883022, 8AA5222, 9000035, 9007999, 9009717, 9009777, 9009997, 9090997,
9099907, 9355555, 9790099, 9900991, 9900997, 9907909, 9909079, 9979009, 9990079, 9990091, 9990907, 9999771,
9999799, 9999979, A000696, A000991, A001091, A006906, A010044, A040041, A0AAA58, A141111, A5222A2,
A600A69, A906606, A909009, A990009, A997701, AA55A52, AAA5552, AAAAA52, 10004747, 10005007, 17000744,
22888823, 28888223, 30010111, 30555777, 31011111, 33000023, 40A00041, 45000055, 47040004, 50377777, 50555553,
5282AAA2, 55505003, 555A5A52, 555AAA2A, 55A5A552, 5AAAAA2A, 60A99999, 70000057, 70070474, 70074704,
70174004, 70700078, 70700474, 70704704, 70710707, 70771007, 70777177, 71074004, 74470001, 77000177, 77070477,
77100077, 77470004, 77700404, 77710007, 77717707, 77748808, 7774A888, 77770078, 77770474, 77774704, 77777008,
77777404, 77777778, 80555055, 88828823, 88888326, 88888823, 8A522222, 90097909, 90700999, 90977777, 97000001,
97000717, 97770007, 99000001, 99000771, 99077001, 99090097, 99777707, 99900097, 99970717, 99999097, 99999707,
A0000058, A0004041, A00055A9, A000A559, A1900001, A5555009, A5A55552, A9700001, A9909006, A9990006,
A9990606, A9999917, A9999966, 100000507, 100035077, 100050777, 100057707, 101111114, 15A000001, 170000447,
300577777, 40000A401, 447771777, 44A444441, 474000004, 477700004, 477777774, 505000003, 55555AA2A,
5555A5A2A, 700000147, 700017004, 700044004, 700077774, 700170004, 701000047, 701700004, 704000044,
704040004, 707070774, 707077704, 707770704, 707777004, 717000004, 717700007, 770000078, 770004704,
770070747, 770070774, 770700008, 770700084, 770707074, 777000044, 777000774, 777717007, 777770477,
777770747, 7777777A4, 77A700008, 888888302, 900000091, 900090799, 970009099, 990990007, 997000077,
999999997, A0000AA58, A00990001, A05555559, A44444111, A44444777, A44477777, A66666669, A90000606,
A99999006, A99999099, 1000007447, 1005000007, 1500000001, ..., 3700000001, ..., 4000000005, ..., 600000A999,
..., A000144444, ..., A900000066, ..., 33333333337, ..., 44444444447, ..., A0000000001, ..., A0014444444, ...,
100000000057, ..., 40000000A0041, ..., A000000014444, ..., A044444444441, ..., A144444444411, ..., 40000000000401,
..., A0000044444441, ..., A00000000444441, ..., 11111111111111111, ..., 14444444444441111, ..., 44444444444444111,
..., 70000000000000004, ..., A1444444444444444, ..., A9999999999999996, ..., 888888888888888883, ...,
1444444444444444444, ..., 7777777777777777771, ..., 4000000000000000A041, ..., 9777777777777777777707,
..., A999999999999999999999, ..., 10000000000000000000747, ..., 3577777777777777777777777, ...,
77700000000000000000000008, ..., A44444444444444444444444441, ..., 1500000000000000000000000007,
..., 40000000000000000000000000041, ..., 440000000000000000000000000001, ...,
999999999999999999999999999999991, ..., 1900000000000000000000000000000000001, ...,
A477777777777777777777777777777777777777777, ..., 444444444444444444444444444444444444444444441, ...,
99777777777777777777777777777777777777777777777777777777777777777, ...,
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000051, ..., 55555555555555555555555555555555555555555555555555555555555
55555555555555555555555555555555555
55555555555555555555555555555555555555555555555555555555555555555552A, ...}

The condensed table for bases b up to 16 is:

b number of quasi-minimal primes base b base-b form of largest known quasi-minimal prime base b length of largest known quasi-minimal prime base b algebraic ((a×bⁿ+c)/d) form of largest known quasi-minimal prime base b

2 1 11 2 3

3 3 111 3 13

4 5 221 3 41

5 22 10₉₃13 96 5⁹⁵+8

6 11 40041 5 5209

7 ≥71 3₁₆1 17 (7¹⁷−5)/2

8 75 4₂₂₀7 221 (4×8²²¹+17)/7

9 ≥144 30₁₁₅₈11 1161 3×9¹¹⁶⁰+10

10 77 50₂₈27 31 5×10³⁰+27

11 ≥895 5₁₆₁2A 163 (11¹⁶³−57)/2

12 106 40₃₉77 42 4×12⁴¹+91

13 ≥2451 80₃₂₀₁₇111 32021 8×13³²⁰²⁰+183

14 ≥596 4D₁₉₆₉₈ 19699 5×14¹⁹⁶⁹⁸−1

15 ≥1151 7₁₅₅97 157 (15¹⁵⁷+59)/2

16 ≥1877 DB₃₂₂₃₄ 32235 (206×16³²²³⁴−11)/15

Q1: Complete my set for bases 7, 9, 11 and prove that they are all complete.

Q2: Find all such primes with length <=1000 for bases 13 through 36.

Q3: Find the set for bases 13 through 36. (This will be a hard problem, e.g. the set for base 23
has a probable prime 9(E^800873), and the set for base 30 has a prime O(T^34205))

On August 2, 2021, Richard Chen added:

See this txt file.

***

Richard Chen wrote on June 2, 2022:

All bases 2<=b<=12 and b=14 are completely solved, except the largest minimal prime in base 11 (5(7^62668), its algebraic form is (57*11^62668-7)/10) is only PRP and not proven prime.
See the attached text file.

***

On Set 13, 2002 Richard Chen wrote:

Now, bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24 are completely solved, and bases 11, 16, 22, 30 are also solved if probable primes are allowed

This is the data for known minimal primes in bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 26, 28, 30, 36 and the unsolved families in bases 13, 17, 19, 21, 26, 28, 36

File 1, File 2.

...
Condensed table for bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 26, 28, 30, 36: (the bases 11, 13, 16, 17, 19, 21, 22, 26, 28, 30, 36 data assumes the primality of the probable primes)

b
number of minimal primes base b

base-b form of the largest known minimal prime base b

length of the largest known minimal prime base b

algebraic ((a*b^n+c)/d) form of the largest known minimal prime base b

number of unsolved families in base b

searching limit of length for the unsolved families in base b (if there are different searching limits for the unsolved families in base b, choose the lowest searching limit)

2 1 11 2 3 0 ---

3 3 111 3 13 0 ---

4 5 221 3 41 0 ---

5 22 1(0^93)13 96 5^95+8 0 ---

6 11 40041 5 5209 0 ---

7 71 (3^16)1 17 (7^17−5)/2 0 ---

8 75 (4^220)7 221 (4×8^221+17)/7 0 ---

9 151 3(0^1158)11 1161 3×9^1160+10 0 ---

10 77 5(0^28)27 31 5×10^30+27 0 ---

11 1068 5(7^62668) 62669 (57×11^62668−7)/10 0 ---

12 106 4(0^39)77 42 4×12^41+91 0 ---

13 3195~3197 8(0^32017)111 32021 8×13^32020+183 2 139000

14 650 4(D^19698) 19699 5×14^19698−1 0 ---

15 1284 (7^155)97 157 (15^157+59)/2 0 ---

16 2347 (3^116137)AF 116139 (16^116139+619)/5 0 ---

17 10407~10428 E9(B^44732) 44734 (3963×17^44732−11)/16 21 46000

18 549 C(0^6268)C5 6271 12×18^6270+221 0 ---

19 31400~31435 D17D(0^19750)1 19755 89674×19^19751+1 35 20000

20 3314 G(0^6269)D 6271 16×20^6270+13 0 ---

21 13373~13395 5D(0^19848)1 19851 118×21^19849+1 23 20000

22 8003 B(K^22001)5 22003 (251×22^22002−335)/21 0 ---

24 3409 N00(N^8129)LN 8134 13249×24^8131−49 0 ---

26 25250~25259 (5^19391)6F 19393 (26^19393+179)/5 9 20000

28 25528~25529 O4(O^94535)9 94538 (6092×28^94536−143)/9 1 543000

30 2619 O(T^34205) 34206 25×30^34205−1 0 ---

36 35256~35263 (J^10117)LJ 10119 (19×36^10119+2501)/35 7 20000

***