Problems & Puzzles: Puzzles

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, 
777744444417777777777771555555555555525, 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 ((abn+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 109313 96 595+8
6 11 40041 5 5209
7 ≥71 3161 17 (717−5)/2
8 75 42207 221 (48221+17)/7
9 ≥144 30115811 1161 391160+10
10 77 502827 31 51030+27
11 ≥895 51612A 163 (11163−57)/2
12 106 403977 42 41241+91
13 ≥2451 8032017111 32021 81332020+183
14 ≥596 4D19698 19699 51419698−1
15 ≥1151 715597 157 (15157+59)/2
16 ≥1877 DB32234 32235 (2061632234−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.

 

***

 

 

 


Records   |  Conjectures  |  Problems  |  Puzzles