|
![Old](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="10" height="11"><rect fill-opacity="0"/></svg> "Old")
2019-11-25, 18:28
|
#1 |
![sweety439's Avatar](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="96" height="96"><rect fill-opacity="0"/></svg> "sweety439's Avatar")
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
367610 Posts |
![Default](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="16" height="16"><rect fill-opacity="0"/></svg> "Default")
Minimal set of the strings for primes with at least two digits
Edit:
The article for this project: https://docs.google.com/document/d/e...W67N_vn96J/pub (new link from GoogleDrive: https://docs.google.com/document/d/1...it?usp=sharing) The GitHub page for this project: https://github.com/xayahrainie4793/n...e-digit-primes The Excel file for the smallest (probable) primes in families which always produce minimal primes (start with b+1) for 2<=b<=1024: https://docs.google.com/spreadsheets...RwmKME/pubhtml ----------------------------------------------------------I am the dividing line---------------------------------------------------------- http://primes.utm.edu/glossary/xpage/MinimalPrime.html In 1996, Jeffrey Shallit [Shallit96] suggested that we view prime numbers as strings of digits. He then used concepts from formal language theory to define an interesting set of primes called the minimal primes: 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 [Lothaire83]. 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: Code:
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}
7: {2, 3, 5, 10, 14, 16, 41, 61, 11111}
8: {2, 3, 5, 7, 111, 141, 161, 401, 661, 4611, 6101, 6441, 60411, 444641, 444444441}
9: {2, 3, 5, 7, 14, 18, 41, 81, 601, 661, 1011, 1101}
10: {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}
11: {2, 3, 5, 7, 10, 16, 18, 49, 61, 81, 89, 94, 98, 9A, 199, 1AA, 414, 919, A1A, AA1, 11A9, 66A9, A119, A911, AAA9, 11144, 11191, 1141A, 114A1, 1411A, 144A4, 14A11, 1A114, 1A411, 4041A, 40441, 404A1, 4111A, 411A1, 44401, 444A1, 44A01, 6A609, 6A669, 6A696, 6A906, 6A966, 90901, 99111, A0111, A0669, A0966, A0999, A0A09, A4401, A6096, A6966, A6999, A9091, A9699, A9969, 401A11, 404001, 404111, 440A41, 4A0401, 4A4041, 60A069, 6A0096, 6A0A96, 6A9099, 6A9909, 909991, 999901, A00009, A60609, A66069, A66906, A69006, A90099, A90996, A96006, A96666, 111114A, 1111A14, 1111A41, 1144441, 14A4444, 1A44444, 4000111, 4011111, 41A1111, 4411111, 444441A, 4A11111, 4A40001, 6000A69, 6000A96, 6A00069, 9900991, 9990091, A000696, A000991, A006906, A040041, A141111, A600A69, A906606, A909009, A990009, 40A00041, 60A99999, 99000001, A0004041, A9909006, A9990006, A9990606, A9999966, 40000A401, 44A444441, 900000091, A00990001, A44444111, A66666669, A90000606, A99999006, A99999099, 600000A999, A000144444, A900000066, A0000000001, A0014444444, 40000000A0041, A000000014444, A044444444441, A144444444411, 40000000000401, A0000044444441, A00000000444441, 11111111111111111, 14444444444441111, 44444444444444111, A1444444444444444, A9999999999999996, 1444444444444444444, 4000000000000000A041, A999999999999999999999, A44444444444444444444444441, 40000000000000000000000000041, 440000000000000000000000000001, 999999999999999999999999999999991, 444444444444444444444444444444444444444444441}
12: {2, 3, 5, 7, B, 11, 61, 81, 91, 401, A41, 4441, A0A1, AAAA1, 44AAA1, AAA0001, AA000001}
Now, let's consider: if our set is the set of prime numbers > b written in radix b, then we get the sets: Code:
b, we get the set
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}
7: {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, ...}
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, 44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444447}
9: {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, ..., 100000000000507, ..., 5111111111111161, ..., 8888888888888888888335, ..., 30000000000000000000051, ..., 1000000000000000000000000057, ..., 56111111111111111111111111111111111111, ..., 7666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666662, ..., 27777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777707, ..., 300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011, ...}
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}
11: {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, ..., 45AAAAAAAAAAAAAAAAAAAA, ..., 9777777777777777777707, ..., A999999999999999999999, ..., 10000000000000000000747, ..., 3577777777777777777777777, ..., 10000000000000000000000044, ..., 77700000000000000000000008, ..., A44444444444444444444444441, ..., 1500000000000000000000000007, ..., 40000000000000000000000000041, ..., 440000000000000000000000000001, ..., 999999999999999999999999999999991, ..., 1900000000000000000000000000000000001, ..., 7777777777777777777777777777777777704, ..., A477777777777777777777777777777777777777777, ..., 444444444444444444444444444444444444444444441, ..., 8055555555555555555555555555555555555555555555555555555555555, ..., 44777777777777777777777777777777777777777777777777777777777777777, ..., 99777777777777777777777777777777777777777777777777777777777777777, ..., 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051, ..., 555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555552A, ..., 5077777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777, ..., 77777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777744, ..., 55777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777, ...}
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}
Can someone complete my base 7, 9, 11 set? Also find the sets of bases 13 to 36. Last fiddled with by sweety439 on 2021-12-23 at 09:40 |
![sweety439 is offline](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="15" height="15"><rect fill-opacity="0"/></svg> "sweety439 is offline")
|
![Reply With Quote](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="70" height="22"><rect fill-opacity="0"/></svg> "Reply With Quote")
|
|
2019-11-26, 05:46
|
#2 |
|
Romulan Interpreter
![LaurV's Avatar](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="100" height="100"><rect fill-opacity="0"/></svg> "LaurV's Avatar")
"name field"
Jun 2011
Thailand
1026010 Posts |
Your sets for 2 and 3 are complete, but the others are not.
For example, all Fermat numbers that may be prime are of the form "1000.....1" in base 4, and additionally, you will have and endless number of combinations of patterns of 0 and 1 that may be prime, and yet not appear in your list, so your base 4 may look like: Code:
List(["2", "3", "11", "101", "10001", "100000001", "100001001001001", "100100100001001"]) Code:
List(["2", "3", "10", "111", "401", "414", "1404", "4041", "14004", "14404", "14411", "14444", "40041", "40441", "41141", "44001 ", "44441", "144404", "404001", "404441", "1440044", "1444114", "4000001", "4000144", "4001411", "4114001", "11440001", "1400000 4", "14000114", "14000404", "14000411", "40400001", "40400014", "40400041", "44000441", "44400014", "44440001", "140000404", "14 0000411", "140000444", "140011411", "140014001", "141144004", "144000044", "144000114", "144000444", "400040014", "400114001", " 400140004", "400144004", "404000041", "404004001", "404040001", "404400001", "404400041", "440040001", "1400040004", "1400044114 ", "1411400011", "1440000404", "1440004114", "1444000114", "1444004404", "4000000041", "4000400041", "4000400441", "4004400041", "4040000041", "4040440001", "4044000041", "4044004001", "4400000001", "4400011441", "4404000441", "4444400041", "11400000001", "11400000041", "11400114441", "11440000144", "11444000014", "14000011444", "14000014441", "14000040011", "14000040044", "1400004 4004", "14000044114", "14000140001", "14001440001", "14114000011", "14114000444", "14400000004", "14400000011", "14400001441", " 14400004114", "14400040044", "14400400141", "14400400444", "14400404044", "14440000004", "14440004044", "14440040004", "14440040 444", "40000000041", "40000001411", "40000004441", "40000040014", "40000141144", "40000400441", "40001400004", "40004001141", "4 0004004441", "40011400001", "40014000044", "40014001144", "40014440044", "40040000001", "40040040001", "40044004001", "400440044 41", "40044400001", "40044411441", "40400004441", "40440400441", "40444000041", "40444004441", "41144400001", "44000400014", "44 004440001", "44040004441", "44044040001", "44114000441", "44114400001", "44400001444", "44400004001", "44400004441", "4444000000 1", "44440000144", "44444000041"]) Last fiddled with by LaurV on 2019-11-26 at 05:55 |
|
|
|
|
2019-11-26, 06:05
|
#3 | ||
|
Jan 2017
32·17 Posts |
Quote:
Quote:
|
||
|
|
|
|
2019-11-26, 06:10
|
#4 |
|
Romulan Interpreter
"name field"
Jun 2011
Thailand
101000000101002 Posts |
Ok, scratch the former post, I am stupid.
It looked odd, and I could not believe those paper were right, then I went and read them (skimmed) and realized the sequence does not need to be consecutive. In fact, you stated as much as that, and your example with 251664 shows very clearly what you mean. Sorry for being stupid  (in fact, my excuse is that you post so much rubbish here that I don't read your post more than fast skimming mode  )Give me 5 minutes... (look how I am spending my lunch break!) (edit @uau: crosspost, I was talking to sweety) Last fiddled with by LaurV on 2019-11-26 at 06:12 |
|
|
|
|
2019-11-26, 06:46
|
#5 |
|
Romulan Interpreter
"name field"
Jun 2011
Thailand
240248 Posts |
Ok, here is the code, and I searched much higher, there are no new numbers.
Code:
\\finds text substrings in text strings, or small-sub-vecteors in large small-vectors :P
\\(kind of efficient, but it still could be optimized...)
find(subtxt,txt,startfrom=1)=
{
my(i,j,s=Vecsmall(subtxt), t=Vecsmall(txt));
i=startfrom-1;
while(i<=#t-#s,
j=1;
while(j<=#s,
if(s[j]!=t[i+j],
break
);
j++
);
if(j>#s,
return(i+1)
);
i++
);
return(0);
}
\\similar, but the strings do not need to be consecutive
findweak(subtxt,txt,startfrom=1)=
{
my(i,j,s=Vecsmall(subtxt), t=Vecsmall(txt));
i=startfrom;
j=1;
while(i<=#t && j<=#s,
if(s[j]==t[i],
j++
);
i++
);
if(j>#s,
return(1),
return(0)
);
}
\\base from 2 to 36, no validation!
bprint(n,base=10)=
{
if(base==10,
return(Str(n))
);
my(v=digits(n,base));
for(i=1,#v,
if(v[i]<10,
v[i]+=48,
v[i]+=55
)
);
return(Strchr(v));
}
minprime(startfrom=2, base=10)=
{
my(n,k,x,cnt);
lstminprimes=List([]);
n=nextprime(startfrom);
listput(lstminprimes,bprint(n,base));
print(lstminprimes);
while(1, \\stop it with ctrl+c when fed-up with it, etc
n=nextprime(n+1);
x=bprint(n,base);
k=1;
while(k<=#lstminprimes,
\\ if(find(lstminprimes[k],x),
if(findweak(lstminprimes[k],x),
break
);
k++
);
if(k>#lstminprimes,
listput(lstminprimes,x);
print(lstminprimes)
);
cnt++;
if(cnt%10000==0,
printf("...%d...%c",n,13)
)
);
}
|
|
|
|
|
2019-11-26, 11:21
|
#6 |
|
Romulan Interpreter
"name field"
Jun 2011
Thailand
101000000101002 Posts |
I let that script running in background for 8, during I was doing some real job-related work, and it still produced 77774444441.
Meantime I realized that it is terrible inefficient, and it can be done much cleverer. So. factory stopped for now, I may revisit it in the future (probably weekend). I also have an idea how 7 and 8 (starting from 2 digits) can be "proved" formally. I go home now, 18:20 here. Last fiddled with by LaurV on 2019-11-26 at 11:23 |
|
|
|
|
2019-11-28, 11:29
|
#7 |
|
Romulan Interpreter
"name field"
Jun 2011
Thailand
22·33·5·19 Posts |
I found an easy way to generate those sets, and to prove that they are complete.
For the "starting from two digits" version, neither one of the exposed sets for 7 and 8 are complete. Some larger primes are still lurking in the dark there. I have the complete sets for both 8, and 7 for the both cases when the base itself is included in the set or not*, but I don't want to spoil the puzzle, this is an interesting little problem... hehe... Hint: Code:
gp > a=(7^17-5)/2 %1 = 116315256993601 gp > isprime(a) %2 = 1 gp > digits(a,7) %3 = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1] gp > *when the base is prime, like for 5 and 7, the sets are different; including the base results in automatic elimination of all possible extension numbers with "0 after 1" from the set, which is quite restrictive, so I also calculated the lists for the "base is not included" version, i.e. base-5 starting from 6, and base-7 starting from 8; in this case, for example, base-5 will include numbers like 104 and 10103 which are prime, and base-7 list will include 1022, 1051, 1202, .... 1100021 ... etc, they are "enriched" compared with the case when the first "10" is included. So I have the complete list for 8, and the complete two lists for 7, the normal one, and the "enriched" one. Base-5 is easy, in any case. Last fiddled with by LaurV on 2019-11-28 at 11:33 |
|
|
|
|
2019-11-28, 22:16
|
#8 | |
|
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
22·919 Posts |
Quote:
|
|
|
|
|
|
2019-11-28, 22:40
|
#9 | |
|
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
367610 Posts |
Quote:
Code:
a(n,k,b)=v=[];for(r=1,length(digits(n,b)),if(r+length(digits(k,2))-length(digits(n,b))>0 && digits(k,2)[r+length(digits(k,2))-length(digits(n,b))]==1,v=concat(v,digits(n,b)[r])));fromdigits(v,b)
g(n)=if(n<10,n+48,if(n<36,n+55,if(n<62,n+61,if(n<77,n-29,if(n<84,n-19,if(n<90,n+7,if(n<94,n+33,n+67)))))))
f(n,b)=for(k=1,length(digits(n,b)),print1(Strchr(g(digits(n,b)[k]))))
is(n,b)=for(k=1,2^length(digits(n,b))-2,if(ispseudoprime(a(n,k,b)) && a(n,k,b)>=b+1,return(0)));1
c(b)=forprime(p=b+1,2^32,if(is(p,b),f(p,b);print1(", ")))
Code:
a(n,k,b)=v=[];for(r=1,length(digits(n,b)),if(r+length(digits(k,2))-length(digits(n,b))>0 && digits(k,2)[r+length(digits(k,2))-length(digits(n,b))]==1,v=concat(v,digits(n,b)[r])));fromdigits(v,b)
g(n)=if(n<10,n+48,if(n<36,n+55,if(n<62,n+61,if(n<77,n-29,if(n<84,n-19,if(n<90,n+7,if(n<94,n+33,n+67)))))))
f(n,b)=for(k=1,length(digits(n,b)),print1(Strchr(g(digits(n,b)[k]))))
is(n,b)=for(k=1,2^length(digits(n,b))-2,if(ispseudoprime(a(n,k,b)),return(0)));1
c(b)=forprime(p=2,2^32,if(is(p,b),f(p,b);print1(", ")))
Last fiddled with by sweety439 on 2021-07-20 at 13:44 |
|
|
|
|
|
2019-11-29, 02:17
|
#10 |
|
Romulan Interpreter
"name field"
Jun 2011
Thailand
281416 Posts |
I didn't look yet how good is your code, but my former one is lousy, so there are chances that yours is better. I mean, not the code, but my method itself was lousy, to look at all primes one by one. The authors of that paper you linked describe a method which is much better and somehow similar to what I am doing now.
Right now, I split the problem in two steps, first I let the zero apart, and solve the problem with "digits" from 1 to b-1, by starting from the end with all possible cases in a set. Starting from the end or from the beginning makes no difference, but in the case the base is even, I only have n/2 elements in the initial set (because numbers ending in 2, 4, 6, etc, can never be prime), so the search dimension is reduced in half. Then, for all elements in set, I check what digit I can add in front of them and still avoiding conflicts. If any of the resulting numbers is prime, I add it to the set. Here is where the algorithm "strikes", because I can do this in about linear time, by creating a matrix with the possible candidates, and then eliminating them from the matrix, by different criteria (like, it produces conflict, it is a prime and I add it to the list, or it is always composite regardless of how you extend it, etc), and sometimes full rows and columns can be eliminated. This gives me the complete set, excluding the numbers that contain zero, in just minutes. The second part comes from the realization that the numbers that contain zero and have to be in the set, if we delete zeroes from them, the new created are (1) still not in the set, and (2) can not be covered with numbers in the set, and (3) are the same magnitude as the numbers in the set except maybe the first digit, that can repeat indefinitely till the first prime is found. The (3) is very important (and it can be proved) so the second part of the algorithm is to create a list with all such numbers (like 5-6 digit numbers in our case) and see which one becomes a prime when it is "stuffed" with zeroes, which is piece of cake. Mind that the zeros have to be "between" the digits, as "leading zeros do not count"(TM) and numbers ending in zero in any base are not prime. Last fiddled with by LaurV on 2019-11-29 at 02:25 |
|
|
|
|
2019-11-29, 06:50
|
#11 |
|
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
22·919 Posts |
This is the C code for this problem: (need run with GMP)
This code computes minimal primes for bases between l and h, possibly along with a set of unsolved families. This code can be used for bases <= 64 (0-9 for digit values 0-9, A-Z for digit values 10-35, a-z for digit values 36-61, # for digit value 62, $ for digit value 63) Copy this C code and name "minimal.c" Usage: minimal l h To resume base b from iter i: minimal resume b i Note: This code will not remove the families with all or partial algebraic factorization of x^4+4*y^4 (as I do not know how to add it), thus this code will print base 16 unsolved families "C*D" and "C*DD" (both with full algebraic factorization of x^4+4*y^4) and base 55 unsolved family "jP0*1" (with partial algebraic factorization of x^4+4*y^4), although these three families can be ruled out as only contain composites (only count numbers > base). Code:
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <string.h>
#define MAXSTRING 512
#ifdef PRINTALL
#define PRINTDATA
#define PRINTITER
#define PRINTSUMMARY
#define PRINTDIVISOR
#define PRINTDIVISORTWO
#define PRINTDIVISORTHREE
#define PRINTDIVISORFOUR
#define PRINTDIVISORFIVE
#define PRINTDIVISORSQUARE
#define PRINTDIVISORCUBE
#define PRINTSTATS
#define PRINTUNSOLVED
#define PRINTSPLIT
#define PRINTSPLITDOUBLE
#define PRINTSPLITTRIPLE
#define PRINTSPLITQUAD
#define PRINTSPLITQUINT
#define PRINTPRIMES
#define PRINTSUBWORD
#define PRINTEXPLORE
#define PRINTTRIVIAL
#define PRINTRESUME
#define PRINTDIVISOREXT
#define PRINTSPLITEXT
#endif
#if defined(PRINTDATA) || defined(PRINTITER)
#include <sys/stat.h>
#endif
typedef struct
{ int len;
int* numrepeats;
char* digit;
char** repeats;
} family;
typedef struct
{ int size;
char** primes;
} kernel;
typedef struct
{ int size;
family* fam;
char* split;
} list;
void familystring(char* str, family p);
void clearfamily(family* f);
void copyfamily(family* newf, family f);
void adddigit(family* f, char d, char* r, int n);
void familyinit(family* p);
void addtolist(list* l, family f, char split);
void simplefamilystring(char* str, family p);
int issimple(family f);
int base;
int depth;
int iter;
kernel K;
int prsize;
char* pr;
void listinit(list* l)
{ l->size = 0;
l->fam = NULL;
l->split = NULL;
}
void copylist(list* out, list in)
{ out->size = in.size;
out->fam = malloc(in.size*sizeof(family));
out->split = malloc(in.size*sizeof(char));
for(int i=0; i<in.size; i++)
{ familyinit(&(out->fam[i]));
copyfamily(&(out->fam[i]), in.fam[i]);
out->split[i] = in.split[i];
}
}
void clearlist(list* l)
{ for(int i=0; i<l->size; i++)
clearfamily(&(l->fam[i]));
free(l->fam);
free(l->split);
listinit(l);
}
void removedupes(list* unsolved)
{ if(unsolved->size==0)
return;
list newlist;
listinit(&newlist);
int n = 1;
char** strlist = malloc(n*sizeof(char*));
int* listpos = malloc(n*sizeof(int));
char* str = malloc(MAXSTRING*sizeof(char));
if(issimple(unsolved->fam[0]))
simplefamilystring(str, unsolved->fam[0]);
else
familystring(str, unsolved->fam[0]);
strlist[0] = str;
listpos[0] = 0;
addtolist(&newlist, unsolved->fam[0], unsolved->split[0]);
for(int i=1; i<unsolved->size; i++)
{ str = malloc(MAXSTRING*sizeof(char));
if(issimple(unsolved->fam[i]))
simplefamilystring(str, unsolved->fam[i]);
else
familystring(str, unsolved->fam[i]);
int addedtolist = 0;
char* temp;
char* last;
int inttemp;
int intlast;
for(int j=0; j<n; j++)
{ if(addedtolist)
{ temp = strlist[j];
strlist[j] = last;
last = temp;
inttemp = listpos[j];
listpos[j] = intlast;
intlast = inttemp;
}
else if(strcmp(str,strlist[j])>0)
{ addedtolist = 1;
last = strlist[j];
strlist[j] = str;
intlast = listpos[j];
listpos[j] = n;
addtolist(&newlist, unsolved->fam[i], unsolved->split[i]);
}
else if(strcmp(str,strlist[j])==0)
{ if(issimple(unsolved->fam[i]))
{ char str1[MAXSTRING], str2[MAXSTRING];
familystring(str1, unsolved->fam[i]);
familystring(str2, newlist.fam[listpos[j]]);
if(strlen(str1)<strlen(str2))
{ clearfamily(&(newlist.fam[listpos[j]]));
copyfamily(&(newlist.fam[listpos[j]]), unsolved->fam[i]);
}
}
break;
}
else if(j==n-1)
{ addedtolist = 1;
last = str;
intlast = n;
addtolist(&newlist, unsolved->fam[i], unsolved->split[i]);
}
}
if(addedtolist)
{ n++;
strlist = realloc(strlist, n*sizeof(char*));
strlist[n-1] = last;
listpos = realloc(listpos, n*sizeof(int));
listpos[n-1] = intlast;
}
else
free(str);
}
clearlist(unsolved);
copylist(unsolved, newlist);
clearlist(&newlist);
for(int i=0; i<n; i++)
free(strlist[i]);
free(strlist);
free(listpos);
}
int issimple(family f)
{ int hasrepeat = 0;
for(int i=0; i<f.len; i++)
{ if(f.numrepeats[i]>1)
return 0;
if(f.numrepeats[i]==1)
{ if(hasrepeat)
return 0;
hasrepeat = 1;
}
}
return (hasrepeat==1);
}
int onlysimple(list l)
{ for(int i=0; i<l.size; i++)
{ if(!issimple(l.fam[i]))
return 0;
}
return 1;
}
void printlist(list l)
{ for(int i=0; i<l.size; i++)
{ char str[MAXSTRING];
familystring(str, l.fam[i]);
printf("%s\n", str);
}
}
void simpleprintlist(list l)
{ for(int i=0; i<l.size; i++)
{ char str[MAXSTRING];
simplefamilystring(str, l.fam[i]);
printf("%s\n", str);
}
}
void addtolist(list* l, family f, char split)
{ int size = ++l->size;
l->fam = realloc(l->fam, size*sizeof(family));
familyinit(&((l->fam)[size-1]));
copyfamily(&((l->fam)[size-1]), f);
l->split = realloc(l->split, size*sizeof(char));
l->split[size-1] = split;
}
void kernelinit()
{ K.size = 0;
K.primes = NULL;
}
void addtokernel(char* p)
{ int size = ++K.size;
K.primes = realloc(K.primes, size*sizeof(char*));
K.primes[size-1] = p;
}
void clearkernel()
{ for(int i=0; i<K.size; i++)
free(K.primes[i]);
free(K.primes);
kernelinit();
}
int nosubword(char* p)
{ for(int i=0; i<K.size; i++)
{ int k = 0;
for(int j=0; j<strlen(p); j++)
{ if(K.primes[i][k]==p[j])
k++;
if(k==strlen(K.primes[i]))
return 0;
}
}
return 1;
}
int nosubwordskip(char* p, int skip)
{ for(int i=0; i<K.size; i++)
{ if(i==skip)
continue;
int k = 0;
for(int j=0; j<strlen(p); j++)
{ if(K.primes[i][k]==p[j])
k++;
if(k==strlen(K.primes[i]))
return 0;
}
}
return 1;
}
int isprime(char* p)
{ mpz_t temp;
mpz_init(temp);
mpz_set_str(temp, p, base);
if(mpz_probab_prime_p(temp, 25) > 0 && temp > base)
{ //gmp_printf("%Zd is prime\n", temp);
mpz_clear(temp);
return 1;
}
else
{ //gmp_printf("%Zd is not prime\n", temp);
mpz_clear(temp);
return 0;
}
}
int newminimal(char* p)
{ if(!nosubword(p))
return 0;
return isprime(p);
}
void familyinit(family* p)
{ p->len = 0;
p->numrepeats = NULL;
p->digit = NULL;
p->repeats = NULL;
}
void adddigit(family* f, char d, char* r, int n)
{ int len = ++f->len;
f->digit = realloc(f->digit, len*sizeof(char));
f->digit[len-1] = d;
f->numrepeats = realloc(f->numrepeats, len*sizeof(int));
f->numrepeats[len-1] = n;
f->repeats = realloc(f->repeats, len*sizeof(char*));
f->repeats[len-1] = r;
}
void clearfamily(family* f)
{ free(f->digit);
for(int i=0; i<f->len; i++)
free(f->repeats[i]);
free(f->numrepeats);
free(f->repeats);
familyinit(f);
}
char digitchar(unsigned char digit)
{ if(digit==255)
return 0;
else if(digit==63)
return '$';
else if(digit==62)
return '#';
else if(digit>=36)
return digit+'a'-36;
else if(digit>=10)
return digit+'A'-10;
else
return digit+'0';
}
char invdigitchar(char input)
{ if(input>='0' && input<='9')
return input-'0';
else if(input>='A' && input<='Z')
return input-'A'+10;
else if(input>='a' && input<='z')
return input-'a'+36;
else if(input=='#')
return 62;
else if(input=='$')
return 63;
}
void familystring(char* str, family p)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
{ sprintf(str, "%s%c", str, digitchar(p.digit[i]));
if(p.numrepeats[i]>0)
{ sprintf(str, "%s{", str);
for(int j=0; j<p.numrepeats[i]; j++)
sprintf(str, "%s%c", str, digitchar(p.repeats[i][j]));
sprintf(str, "%s}*", str);
}
}
}
void simplefamilystring(char* str, family p)
{ sprintf(str, "%c", 0);
char repeateddigit;
int repeatedpos;
for(int i=0; i<p.len; i++)
if(p.numrepeats[i]==1)
{ repeateddigit = p.repeats[i][0];
repeatedpos = i;
break;
}
int j=-1;
for(int i=repeatedpos; i>=0; i--)
if(p.digit[i]!=repeateddigit && (unsigned char)p.digit[i]!=255)
{ j = i;
break;
}
int k=p.len;
for(int i=repeatedpos+1; i<p.len; i++)
if(p.digit[i]!=repeateddigit && (unsigned char)p.digit[i]!=255)
{ k = i;
break;
}
for(int i=0; i<=j; i++)
sprintf(str, "%s%c", str, digitchar(p.digit[i]));
sprintf(str, "%s%c*", str, digitchar(repeateddigit));
for(int i=k; i<p.len; i++)
sprintf(str, "%s%c", str, digitchar(p.digit[i]));
}
void startinstancestring(char* str, family p, int length)
{ sprintf(str, "%c", 0);
for(int i=0; i<=length; i++)
sprintf(str, "%s%c", str, digitchar(p.digit[i]));
}
void endinstancestring(char* str, family p, int start)
{ sprintf(str, "%c", 0);
for(int i=start+1; i<p.len; i++)
sprintf(str, "%s%c", str, digitchar(p.digit[i]));
}
void emptyinstancestring(char* str, family p)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
sprintf(str, "%s%c", str, digitchar(p.digit[i]));
}
void instancestring(char* str, family p, int x, int y)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
{ sprintf(str, "%s%c", str, digitchar(p.digit[i]));
if(i==x)
sprintf(str, "%s%c", str, digitchar(p.repeats[x][y]));
}
}
void doubleinstancestring(char* str, family p, int x1, int y1, int x2, int y2)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
{ sprintf(str, "%s%c", str, digitchar(p.digit[i]));
if(i==x1)
sprintf(str, "%s%c", str, digitchar(p.repeats[x1][y1]));
if(i==x2)
sprintf(str, "%s%c", str, digitchar(p.repeats[x2][y2]));
}
}
void tripleinstancestring(char* str, family p, int x1, int y1, int x2, int y2, int x3, int y3)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
{ sprintf(str, "%s%c", str, digitchar(p.digit[i]));
if(i==x1)
sprintf(str, "%s%c", str, digitchar(p.repeats[x1][y1]));
if(i==x2)
sprintf(str, "%s%c", str, digitchar(p.repeats[x2][y2]));
if(i==x3)
sprintf(str, "%s%c", str, digitchar(p.repeats[x3][y3]));
}
}
void quadinstancestring(char* str, family p, int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
{ sprintf(str, "%s%c", str, digitchar(p.digit[i]));
if(i==x1)
sprintf(str, "%s%c", str, digitchar(p.repeats[x1][y1]));
if(i==x2)
sprintf(str, "%s%c", str, digitchar(p.repeats[x2][y2]));
if(i==x3)
sprintf(str, "%s%c", str, digitchar(p.repeats[x3][y3]));
if(i==x4)
sprintf(str, "%s%c", str, digitchar(p.repeats[x4][y4]));
}
}
void quintinstancestring(char* str, family p, int x1, int y1)
{ sprintf(str, "%c", 0);
for(int i=0; i<p.len; i++)
{ sprintf(str, "%s%c", str, digitchar(p.digit[i]));
if(i==x1)
{ sprintf(str, "%s%c%c%c%c%c%c%c%c%c%c", str, digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]), digitchar(p.repeats[x1][y1]));
}
}
}
void copyfamily(family* newf, family f)
{ for(int i=0; i<f.len; i++)
{ char* repeatscopy = malloc(f.numrepeats[i]*sizeof(char));
memcpy(repeatscopy, f.repeats[i], f.numrepeats[i]*sizeof(char));
adddigit(newf, f.digit[i], repeatscopy, f.numrepeats[i]);
}
}
int hasdivisor(family p)
{ mpz_t gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty;
mpz_inits(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
char str[MAXSTRING];
int numrepeats = 0;
emptyinstancestring(str, p);
mpz_set_str(empty, str, base);
mpz_set_str(gcd, str, base);
int allsingledigit = 1;
for(int i=0; i<p.len; i++)
{ for(int j=0; j<p.numrepeats[i]; j++)
{ instancestring(str, p, i, j);
mpz_set_str(temp, str, base);
mpz_gcd(gcd, gcd, temp);
if(temp > base)
allsingledigit = 0;
}
if(p.numrepeats[i]>0)
numrepeats++;
}
if(allsingledigit)
return 1;
if(numrepeats==0)
{
#ifdef PRINTDIVISOR
familystring(str, p);
printf("%s is trivial\n", str);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 0;
}
if(mpz_cmp_ui(gcd, 1)>0 && mpz_cmp(empty, gcd)>0)
{
#ifdef PRINTDIVISOR
familystring(str, p);
gmp_printf("%s has a divisor %Zd\n", str, gcd);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
for(int m=0; m<p.len; m++)
{ if(p.numrepeats[m]==0)
continue;
emptyinstancestring(str, p);
mpz_set_str(gcd1, str, base);
for(int i=0; i<p.len; i++)
{ if(i==m)
continue;
for(int j=0; j<p.numrepeats[i]; j++)
{ instancestring(str, p, i, j);
mpz_set_str(temp, str, base);
mpz_gcd(gcd1, gcd1, temp);
}
}
for(int i=0; i<p.numrepeats[m]; i++)
for(int j=0; j<p.numrepeats[m]; j++)
{ doubleinstancestring(str, p, m, i, m, j);
mpz_set_str(temp, str, base);
mpz_gcd(gcd1, gcd1, temp);
}
int gcdbeenset = 0;
for(int n=0; n<p.numrepeats[m]; n++)
{
instancestring(str, p, m, n);
mpz_set_str(temp, str, base);
if(gcdbeenset)
mpz_gcd(gcd2, gcd2, temp);
else
{ mpz_set(gcd2, temp);
gcdbeenset = 1;
}
for(int i=0; i<p.len; i++)
{ if(i==m)
continue;
for(int j=0; j<p.numrepeats[i]; j++)
{ doubleinstancestring(str, p, i, j, m, n);
mpz_set_str(temp, str, base);
mpz_gcd(gcd2, gcd2, temp);
}
}
for(int i=0; i<p.numrepeats[m]; i++)
for(int j=0; j<p.numrepeats[m]; j++)
for(int k=0; k<p.numrepeats[m]; k++)
{ tripleinstancestring(str, p, m, i, m, j, m, k);
mpz_set_str(temp, str, base);
mpz_gcd(gcd2, gcd2, temp);
}
}
if(mpz_cmp_ui(gcd1, 1)>0 && mpz_cmp_ui(gcd2, 1)>0 && mpz_cmp(empty, gcd1)>0 && mpz_cmp(empty, gcd2)>0)
{
#ifdef PRINTDIVISORTWO
familystring(str, p);
gmp_printf("%s has two divisors %Zd and %Zd\n", str, gcd1, gcd2);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
mpz_set_ui(gcd1, 0);
mpz_set_ui(gcd2, 0);
}
int i;
int gcdbeenset = 0;
for(i=0; i<p.len; i++)
{ for(int j=0; j<p.numrepeats[i]; j++)
{ instancestring(str, p, i, j);
mpz_set_str(temp, str, base);
if(gcdbeenset)
mpz_gcd(gcd2, gcd2, temp);
else
{ gcdbeenset = 1;
mpz_set(gcd2, temp);
}
for(int k=0; k<p.len; k++)
for(int l=0; l<p.numrepeats[k]; l++)
for(int n=0; n<p.numrepeats[k]; n++)
{ tripleinstancestring(str, p, i, j, k, l, k, n);
mpz_set_str(temp, str, base);
mpz_gcd(gcd2, gcd2, temp);
}
}
if(p.numrepeats[i]>0)
break;
}
int firstrepeat = i;
if(numrepeats==2)
{ emptyinstancestring(str, p);
mpz_set_str(gcd1, str, base);
for(int i=0; i<p.len; i++)
for(int j=0; j<p.numrepeats[i]; j++)
for(int l=0; l<p.numrepeats[i]; l++)
{ doubleinstancestring(str, p, i, j, i, l);
mpz_set_str(temp, str, base);
mpz_gcd(gcd1, gcd1, temp);
}
gcdbeenset = 0;
for(i=firstrepeat+1; i<p.len; i++)
{ for(int j=0; j<p.numrepeats[i]; j++)
{ instancestring(str, p, i, j);
mpz_set_str(temp, str, base);
if(gcdbeenset)
mpz_gcd(temp2, temp2, temp);
else
{ gcdbeenset = 1;
mpz_set(temp2, temp);
}
for(int k=0; k<p.len; k++)
for(int l=0; l<p.numrepeats[k]; l++)
for(int n=0; n<p.numrepeats[k]; n++)
{ tripleinstancestring(str, p, i, j, k, l, k, n);
mpz_set_str(temp, str, base);
mpz_gcd(temp2, temp2, temp);
}
}
if(p.numrepeats[i]>0)
break;
}
int secondrepeat = i;
gcdbeenset = 0;
for(int j=0; j<p.numrepeats[firstrepeat]; j++)
for(int l=0; l<p.numrepeats[secondrepeat]; l++)
{ doubleinstancestring(str, p, firstrepeat, j, secondrepeat, l);
mpz_set_str(temp, str, base);
if(gcdbeenset)
mpz_gcd(temp3, temp3, temp);
else
{ gcdbeenset = 1;
mpz_set(temp3, temp);
}
}
for(i=0; i<p.numrepeats[firstrepeat]; i++)
for(int j=0; j<p.numrepeats[firstrepeat]; j++)
for(int k=0; k<p.numrepeats[firstrepeat]; k++)
for(int l=0; l<p.numrepeats[secondrepeat]; l++)
{ quadinstancestring(str, p, firstrepeat, i, firstrepeat, j, firstrepeat, k, secondrepeat, l);
mpz_set_str(temp, str, base);
mpz_gcd(temp3, temp3, temp);
}
for(i=0; i<p.numrepeats[firstrepeat]; i++)
for(int j=0; j<p.numrepeats[secondrepeat]; j++)
for(int k=0; k<p.numrepeats[secondrepeat]; k++)
for(int l=0; l<p.numrepeats[secondrepeat]; l++)
{ quadinstancestring(str, p, firstrepeat, i, secondrepeat, j, secondrepeat, k, secondrepeat, l);
mpz_set_str(temp, str, base);
mpz_gcd(temp3, temp3, temp);
}
if(mpz_cmp_ui(gcd1, 1)>0 && mpz_cmp_ui(gcd2, 1)>0 && mpz_cmp(empty, gcd1)>0 && mpz_cmp(empty, gcd2)>0 &&
mpz_cmp_ui(temp2, 1)>0 && mpz_cmp_ui(temp3, 1)>0 && mpz_cmp(empty, temp2)>0 && mpz_cmp(empty, temp3)>0)
{
#ifdef PRINTDIVISORTWONEW
familystring(str, p);
gmp_printf("%s has four divisors %Zd, %Zd, %Zd, and %Zd\n", str, gcd1, gcd2, temp2, temp3);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
}
char end[MAXSTRING], start[MAXSTRING], middle[2];
if(numrepeats==1)
{ for(int i=0; i<p.len; i++)
{ if(p.numrepeats[i]==1)
{ endinstancestring(str, p, i);
int zlen = strlen(str);
mpz_set_str(z, str, base);
mpz_set_ui(y, p.repeats[i][0]);
startinstancestring(str, p, i);
mpz_set_str(x, str, base);
endinstancestring(end, p, i);
sprintf(middle, "%c", digitchar(p.repeats[i][0]));
startinstancestring(start, p, i);
sprintf(str, "%s%s\n", start, end);
mpz_set_str(temp, str, base);
sprintf(str, "%s%s%s\n", start, middle, end);
mpz_set_str(temp2, str, base);
sprintf(str, "%s%s%s%s\n", start, middle, middle, end);
mpz_set_str(temp3, str, base);
sprintf(str, "%s%s%s%s%s\n", start, middle, middle, middle, end);
mpz_set_str(temp4, str, base);
sprintf(str, "%s%s%s%s%s%s\n", start, middle, middle, middle, middle, end);
mpz_set_str(temp5, str, base);
sprintf(str, "%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, end);
mpz_set_str(temp6, str, base);
mpz_gcd(temp, temp, temp4);
mpz_gcd(temp2, temp2, temp5);
mpz_gcd(temp3, temp3, temp6);
if(mpz_cmp_ui(temp, 1)>0 && mpz_cmp_ui(temp2, 1)>0 && mpz_cmp_ui(temp3, 1)>0 && mpz_cmp(empty, temp)>0 && mpz_cmp(empty, temp2)>0 && mpz_cmp(empty, temp3)>0)
{
#ifdef PRINTDIVISORTHREE
familystring(str, p);
gmp_printf("%s has three divisors %Zd, %Zd, and %Zd\n", str, temp, temp2, temp3);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
sprintf(str, "%s%s\n", start, end);
mpz_set_str(temp, str, base);
sprintf(str, "%s%s%s\n", start, middle, end);
mpz_set_str(temp2, str, base);
sprintf(str, "%s%s%s%s\n", start, middle, middle, end);
mpz_set_str(temp3, str, base);
sprintf(str, "%s%s%s%s%s\n", start, middle, middle, middle, end);
mpz_set_str(temp4, str, base);
sprintf(str, "%s%s%s%s%s%s\n", start, middle, middle, middle, middle, end);
mpz_set_str(temp5, str, base);
sprintf(str, "%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, end);
mpz_set_str(temp6, str, base);
sprintf(str, "%s%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, middle, end);
mpz_set_str(temp7, str, base);
sprintf(str, "%s%s%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, middle, middle, end);
mpz_set_str(temp8, str, base);
mpz_gcd(temp, temp, temp5);
mpz_gcd(temp2, temp2, temp6);
mpz_gcd(temp3, temp3, temp7);
mpz_gcd(temp4, temp4, temp8);
if(mpz_cmp_ui(temp, 1)>0 && mpz_cmp_ui(temp2, 1)>0 && mpz_cmp_ui(temp3, 1)>0 && mpz_cmp_ui(temp4, 1)>0 && mpz_cmp(empty, temp)>0 && mpz_cmp(empty, temp2)>0 && mpz_cmp(empty, temp3)>0 && mpz_cmp(empty, temp4)>0)
{
#ifdef PRINTDIVISORFOUR
familystring(str, p);
gmp_printf("%s has four divisors %Zd, %Zd, %Zd, and %Zd\n", str, temp, temp2, temp3, temp4);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
sprintf(str, "%s%s\n", start, end);
mpz_set_str(temp, str, base);
sprintf(str, "%s%s%s\n", start, middle, end);
mpz_set_str(temp2, str, base);
sprintf(str, "%s%s%s%s\n", start, middle, middle, end);
mpz_set_str(temp3, str, base);
sprintf(str, "%s%s%s%s%s\n", start, middle, middle, middle, end);
mpz_set_str(temp4, str, base);
sprintf(str, "%s%s%s%s%s%s\n", start, middle, middle, middle, middle, end);
mpz_set_str(temp5, str, base);
sprintf(str, "%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, end);
mpz_set_str(temp6, str, base);
sprintf(str, "%s%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, middle, end);
mpz_set_str(temp7, str, base);
sprintf(str, "%s%s%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, middle, middle, end);
mpz_set_str(temp8, str, base);
sprintf(str, "%s%s%s%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, middle, middle, middle, end);
mpz_set_str(temp9, str, base);
sprintf(str, "%s%s%s%s%s%s%s%s%s%s%s\n", start, middle, middle, middle, middle, middle, middle, middle, middle, middle, end);
mpz_set_str(temp10, str, base);
mpz_gcd(temp, temp, temp6);
mpz_gcd(temp2, temp2, temp7);
mpz_gcd(temp3, temp3, temp8);
mpz_gcd(temp4, temp4, temp9);
mpz_gcd(temp5, temp5, temp10);
if(mpz_cmp_ui(temp, 1)>0 && mpz_cmp_ui(temp2, 1)>0 && mpz_cmp_ui(temp3, 1)>0 && mpz_cmp_ui(temp4, 1)>0 && mpz_cmp_ui(temp5, 1)>0 && mpz_cmp(empty, temp)>0 && mpz_cmp(empty, temp2)>0 && mpz_cmp(empty, temp3)>0 && mpz_cmp(empty, temp4)>0 && mpz_cmp(empty, temp5)>0)
{
#ifdef PRINTDIVISORFIVE
familystring(str, p);
gmp_printf("%s has five divisors %Zd, %Zd, %Zd, %Zd, and %Zd\n", str, temp, temp2, temp3, temp4, temp5);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
mpz_gcd_ui(temp10, y, base-1);
int g = mpz_get_ui(temp10);
mpz_divexact_ui(temp, y, g);
mpz_set(temp2, temp);
mpz_addmul_ui(temp, x, (base-1)/g);
mpz_ui_pow_ui(temp3, base, zlen);
mpz_mul(temp, temp, temp3);
mpz_mul(temp2, temp2, temp3);
mpz_submul_ui(temp2, z, (base-1)/g);
if(mpz_root(temp3, temp, 2)!=0 && mpz_sgn(temp2)>=0 && mpz_root(temp4, temp2, 2)!=0)
{ mpz_sub(temp5, temp3, temp4);
mpz_set_ui(temp6, base);
if(mpz_cmp_ui(temp5, (base-1)/g)>0 && mpz_root(temp6, temp6, 2)!=0)
{
#ifdef PRINTDIVISORSQUARE
familystring(str, p);
gmp_printf("%s factors as a difference of squares\n", str);
gmp_printf("%s(%s)^n%s = %Zd + %d^%d*%Zd*(%d^n-1)/%d + %d^(n+%d)*%Zd = (%Zd*%d^n-%Zd)/%d = (%Zd*%Zd^n-%Zd)*(%Zd*%Zd^n+%Zd)/%d\n", start, middle, end, z, base, zlen, y, base, base-1, base, zlen, x, temp, base, temp2, (base-1)/g, temp3, temp6, temp4, temp3, temp6, temp4, (base-1)/g);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
else if(mpz_cmp_ui(temp5, (base-1)/g)>0 && mpz_cmp_ui(gcd2, 1)>0 && mpz_cmp(empty, gcd2)>0)
{
#ifdef PRINTDIVISORSQUARE
familystring(str, p);
gmp_printf("%s factors as a difference of squares for even n, and has a factor %Zd for odd n\n", str, gcd2);
gmp_printf("%s(%s)^n%s = %Zd + %d^%d*%Zd*(%d^n-1)/%d + %d^(n+%d)*%Zd = (%Zd*%d^n-%Zd)/%d = (%Zd*%d^(n/2)-%Zd)*(%Zd*%d^(n/2)+%Zd)/%d\n", start, middle, end, z, base, zlen, y, base, base-1, base, zlen, x, temp, base, temp2, (base-1)/g, temp3, base, temp4, temp3, base, temp4, (base-1)/g);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
}
if(mpz_root(temp3, temp, 3)!=0 && mpz_root(temp4, temp2, 3)!=0)
{ mpz_sub(temp5, temp3, temp4);
mpz_set_ui(temp6, base);
if(mpz_cmp_ui(temp5, (base-1)/g)>0 && mpz_root(temp6, temp6, 3)!=0)
{
#ifdef PRINTDIVISORCUBE
familystring(str, p);
gmp_printf("%s factors as a difference of cubes\n", str);
if(mpz_sgn(temp2)>=0)
gmp_printf("%s(%s)^n%s = (%Zd*%d^n-%Zd)/%d = (%Zd*%Zd^n-%Zd)*((%Zd*%Zd^n)^2+%Zd*%Zd^n*%Zd+%Zd^2)/%d\n", start, middle, end, temp, base, temp2, (base-1)/g, temp3, temp6, temp4, temp3, temp6, temp3, temp6, temp4, temp4, (base-1)/g);
else
gmp_printf("%s(%s)^n%s = (%Zd*%d^n-(%Zd))/%d = (%Zd*%Zd^n-(%Zd))*((%Zd*%Zd^n)^2+%Zd*%Zd^n*(%Zd)+(%Zd)^2)/%d\n", start, middle, end, temp, base, temp2, (base-1)/g, temp3, temp6, temp4, temp3, temp6, temp3, temp6, temp4, temp4, (base-1)/g);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
}
if(mpz_root(temp3, temp, 5)!=0 && mpz_root(temp4, temp2, 5)!=0)
{ mpz_sub(temp5, temp3, temp4);
mpz_set_ui(temp6, base);
if(mpz_cmp_ui(temp5, (base-1)/g)>0 && mpz_root(temp6, temp6, 3)!=0)
{
#ifdef PRINTDIVISORFIFTHPOWER
familystring(str, p);
gmp_printf("%s factors as a difference of fifth powers\n", str);
if(mpz_sgn(temp2)>=0)
gmp_printf("%s(%s)^n%s = (%Zd*%d^n-%Zd)/%d = (%Zd*%Zd^n-%Zd)*((%Zd*%Zd^n)^2+%Zd*%Zd^n*%Zd+%Zd^2)/%d\n", start, middle, end, temp, base, temp2, (base-1)/g, temp3, temp6, temp4, temp3, temp6, temp3, temp6, temp4, temp4, (base-1)/g);
else
gmp_printf("%s(%s)^n%s = (%Zd*%d^n-(%Zd))/%d = (%Zd*%Zd^n-(%Zd))*((%Zd*%Zd^n)^4+(%Zd*%Zd^n)^3*(%Zd)+(%Zd*%Zd^n)^2*(%Zd)^2+%Zd*%Zd^n*(%Zd)^3+(%Zd)^4)/%d\n", start, middle, end, temp, base, temp2, (base-1)/g, temp3, temp6, temp4, temp3, temp6, temp3, temp6, temp4, temp4, (base-1)/g);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
}
}
}
}
char residues[30] = {1};
for(int i=0; i<p.len; i++)
{ if((unsigned char)p.digit[i]!=255)
{ char newresidues[30] = {0};
for(int j=0; j<30; j++)
{ if(residues[j]==1)
newresidues[(j*base+p.digit[i])%30] = 1;
}
memcpy(residues, newresidues, 30);
}
int haschanged = 1;
while(haschanged)
{ haschanged = 0;
for(int j=0; j<p.numrepeats[i]; j++)
{ for(int l=0; l<30; l++)
{ if(residues[l]==1 && residues[(l*base+p.repeats[i][j])%30]==0)
{ residues[(l*base+p.repeats[i][j])%30] = 1;
haschanged = 1;
}
}
}
}
}
int coprimeres = 0;
for(int i=0; i<30; i++)
{ if(residues[i]==1)
{ mpz_set_ui(temp, i);
mpz_gcd_ui(temp, temp, 30);
if(mpz_cmp_ui(temp, 1)==0)
coprimeres = 1;
}
}
if(!coprimeres)
{
#ifdef PRINTDIVISOREXT
familystring(str, p);
gmp_printf("\nevery number in %s is divisible by one of 2, 3, or 5\n", str);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
char residues[42] = {1};
for(int i=0; i<p.len; i++)
{ if((unsigned char)p.digit[i]!=255)
{ char newresidues[42] = {0};
for(int j=0; j<42; j++)
{ if(residues[j]==1)
newresidues[(j*base+p.digit[i])%42] = 1;
}
memcpy(residues, newresidues, 42);
}
int haschanged = 1;
while(haschanged)
{ haschanged = 0;
for(int j=0; j<p.numrepeats[i]; j++)
{ for(int l=0; l<42; l++)
{ if(residues[l]==1 && residues[(l*base+p.repeats[i][j])%42]==0)
{ residues[(l*base+p.repeats[i][j])%42] = 1;
haschanged = 1;
}
}
}
}
}
int coprimeres = 0;
for(int i=0; i<42; i++)
{ if(residues[i]==1)
{ mpz_set_ui(temp, i);
mpz_gcd_ui(temp, temp, 42);
if(mpz_cmp_ui(temp, 1)==0)
coprimeres = 1;
}
}
if(!coprimeres)
{
#ifdef PRINTDIVISOREXT
familystring(str, p);
gmp_printf("\nevery number in %s is divisible by one of 2, 3, or 7\n", str);
#endif
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 1;
}
mpz_clears(gcd, temp, gcd1, gcd2, x, y, z, temp2, temp3, temp4, temp5, temp6, temp7, temp8, temp9, temp10, empty, NULL);
return 0;
}
void instancefamily(family* newf, family f, int side, int pos)
{ for(int i=0; i<f.len; i++)
{ char* repeatscopy = malloc(f.numrepeats[i]*sizeof(char));
memcpy(repeatscopy, f.repeats[i], f.numrepeats[i]*sizeof(char));
if(i==pos)
{ if(side==1)
{ adddigit(newf, f.digit[i], NULL, 0);
adddigit(newf, 0, repeatscopy, f.numrepeats[i]);
}
else if(side==0)
{ adddigit(newf, f.digit[i], repeatscopy, f.numrepeats[i]);
adddigit(newf, 0, NULL, 0);
}
}
else
adddigit(newf, f.digit[i], repeatscopy, f.numrepeats[i]);
}
}
int examine(family* f)
{ char* str = malloc(MAXSTRING);
char tempstr[MAXSTRING];
emptyinstancestring(str, *f);
if(!nosubword(str))
{ free(str);
#ifdef PRINTSUBWORD
familystring(tempstr, *f);
printf("%s has a subword in kernel\n", tempstr);
#endif
return 0;
}
else if(isprime(str))
{ addtokernel(str);
#ifdef PRINTPRIMES
familystring(tempstr, *f);
printf("%s has a prime\n", tempstr);
#endif
return 0;
}
free(str);
int trivial = 1;
for(int i=0; i<f->len; i++)
{ int newnumrepeat = 0;
for(int j=0; j<f->numrepeats[i]; j++)
{ char tempstr[MAXSTRING];
instancestring(tempstr, *f, i, j);
if(nosubword(tempstr))
f->repeats[i][newnumrepeat++] = f->repeats[i][j];
}
f->numrepeats[i] = newnumrepeat;
if(newnumrepeat>0)
trivial = 0;
}
// simplify y*y^ny*
char lastdigit = 0;
int dosimplify = 0;
for(int i=0; i<f->len; i++)
{ if(dosimplify==1 && f->numrepeats[i]==1 && f->repeats[i][0]==lastdigit && (lastdigit==f->digit[i] || (unsigned char)f->digit[i]==255))
{ f->repeats[i] = NULL;
f->numrepeats[i] = 0;
}
if((unsigned char)f->digit[i]!=255)
{ if(f->digit[i] != lastdigit)
dosimplify = 0;
lastdigit = f->digit[i];
}
if(f->numrepeats[i]==1)
{ dosimplify = 1;
lastdigit = f->repeats[i][0];
}
else if(f->numrepeats[i]>1)
dosimplify = 0;
}
if(trivial)
{
#ifdef PRINTTRIVIAL
familystring(tempstr, *f);
printf("%s is trivial\n", tempstr);
#endif
return 0;
}
if(hasdivisor(*f))
{ return 0;
}
return 1;
}
int split(family* f, list* unsolved, char insplit)
{ if(insplit==0)
{ addtolist(unsolved, *f, 0);
return 0;
}
for(int i=0; i<f->len; i++)
{ for(int j=0; j<f->numrepeats[i]; j++)
{ char str[MAXSTRING];
doubleinstancestring(str, *f, i, j, i, j);
if(!nosubword(str))
{
family copyf;
familyinit(©f);
copyfamily(©f, *f);
int newnumrepeats = 0;
int removeddigit = copyf.repeats[i][j];
for(int k=0; k<copyf.numrepeats[i]; k++)
{ if(k!=j)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][k];
}
copyf.numrepeats[i] = newnumrepeats;
family newf;
familyinit(&newf);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
addtolist(unsolved, copyf, 2);
addtolist(unsolved, newf, 2);
#ifdef PRINTSPLITDOUBLE
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, copyf);
printf("%s and ", str);
familystring(str, newf);
printf("%s\n", str);
#endif
clearfamily(©f);
clearfamily(&newf);
return 1;
}
tripleinstancestring(str, *f, i, j, i, j, i, j);
if(!nosubword(str))
{
family copyf;
familyinit(©f);
copyfamily(©f, *f);
int newnumrepeats = 0;
int removeddigit = copyf.repeats[i][j];
for(int k=0; k<copyf.numrepeats[i]; k++)
{ if(k!=j)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][k];
}
copyf.numrepeats[i] = newnumrepeats;
family newf;
familyinit(&newf);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
family newf2;
familyinit(&newf2);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf2, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf2, removeddigit, newrepeats, copyf.numrepeats[k]);
newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf2, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
addtolist(unsolved, copyf, 2);
addtolist(unsolved, newf, 2);
addtolist(unsolved, newf2, 2);
#ifdef PRINTSPLITTRIPLE
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, copyf);
printf("%s and ", str);
familystring(str, newf);
printf("%s and ", str);
familystring(str, newf2);
printf("%s\n", str);
#endif
clearfamily(©f);
clearfamily(&newf);
clearfamily(&newf2);
return 1;
}
quadinstancestring(str, *f, i, j, i, j, i, j, i, j);
if(!nosubword(str))
{
family copyf;
familyinit(©f);
copyfamily(©f, *f);
int newnumrepeats = 0;
int removeddigit = copyf.repeats[i][j];
for(int k=0; k<copyf.numrepeats[i]; k++)
{ if(k!=j)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][k];
}
copyf.numrepeats[i] = newnumrepeats;
family newf;
familyinit(&newf);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
family newf2;
familyinit(&newf2);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf2, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf2, removeddigit, newrepeats, copyf.numrepeats[k]);
newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf2, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
family newf3;
familyinit(&newf3);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf3, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf3, removeddigit, newrepeats, copyf.numrepeats[k]);
newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf3, removeddigit, newrepeats, copyf.numrepeats[k]);
newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf3, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
addtolist(unsolved, copyf, 2);
addtolist(unsolved, newf, 2);
addtolist(unsolved, newf2, 2);
addtolist(unsolved, newf3, 2);
#ifdef PRINTSPLITQUAD
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, copyf);
printf("%s and ", str);
familystring(str, newf);
printf("%s and ", str);
familystring(str, newf2);
printf("%s and ", str);
familystring(str, newf3);
printf("%s\n", str);
#endif
clearfamily(©f);
clearfamily(&newf);
clearfamily(&newf2);
clearfamily(&newf3);
return 1;
}
quintinstancestring(str, *f, i, j);
if(!nosubword(str))
{
family copyf;
familyinit(©f);
copyfamily(©f, *f);
int newnumrepeats = 0;
int removeddigit = copyf.repeats[i][j];
for(int k=0; k<copyf.numrepeats[i]; k++)
{ if(k!=j)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][k];
}
copyf.numrepeats[i] = newnumrepeats;
addtolist(unsolved, copyf, 2);
for(int l=1; l<=9; l++)
{
family newf;
familyinit(&newf);
for(int k=0; k<copyf.len; k++)
{ char* newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, copyf.digit[k], newrepeats, copyf.numrepeats[k]);
if(k==i)
{ for(int m=0; m<l; m++)
{ newrepeats = malloc(copyf.numrepeats[k]*sizeof(char));
memcpy(newrepeats, copyf.repeats[k], copyf.numrepeats[k]*sizeof(char));
adddigit(&newf, removeddigit, newrepeats, copyf.numrepeats[k]);
}
}
}
addtolist(unsolved, newf, 2);
clearfamily(&newf);
}
clearfamily(©f);
#ifdef PRINTSPLITQUINT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits ten ways\n", str);
#endif
return 1;
}
if(iter>5)
{ mpz_t gcd, empty, temp;
mpz_inits(gcd, empty, temp, NULL);
emptyinstancestring(str, *f);
mpz_set_str(empty, str, base);
mpz_set_str(gcd, str, base);
for(int ii=0; ii<f->len; ii++)
{ for(int jj=0; jj<f->numrepeats[ii]; jj++)
{ instancestring(str, *f, ii, jj);
mpz_set_str(temp, str, base);
if(i!=ii || j!=jj)
mpz_gcd(gcd, gcd, temp);
}
}
if(mpz_cmp_ui(gcd, 1)>0 && mpz_cmp(empty, gcd)>0)
{ mpz_clears(gcd, empty, temp, NULL);
family copyf;
familyinit(©f);
for(int ii=0; ii<f->len; ii++)
{ char* repeatscopy = malloc(f->numrepeats[ii]*sizeof(char));
memcpy(repeatscopy, f->repeats[ii], f->numrepeats[ii]*sizeof(char));
adddigit(©f, f->digit[ii], repeatscopy, f->numrepeats[ii]);
if(i==ii)
{ repeatscopy = malloc(f->numrepeats[ii]*sizeof(char));
memcpy(repeatscopy, f->repeats[ii], f->numrepeats[ii]*sizeof(char));
adddigit(©f, f->repeats[i][j], repeatscopy, f->numrepeats[i]);
}
}
addtolist(unsolved, copyf, 2);
#ifdef PRINTSPLITEXT
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, copyf);
printf("%s\n", str);
#endif
clearfamily(©f);
return 1;
}
}
}
}
addtolist(unsolved, *f, 1);
return 0;
}
int split2(family* f, list* unsolved, char insplit)
{ if(insplit==0)
{ addtolist(unsolved, *f, 0);
return 0;
}
for(int i=0; i<f->len; i++)
{ for(int j=0; j<f->numrepeats[i]; j++)
{ for(int m=i; m<f->len; m++)
{ for(int k=0; k<f->numrepeats[m]; k++)
{ if(m==i && j<=k)
continue;
char str1[MAXSTRING];
char str2[MAXSTRING];
char str3[MAXSTRING];
char str4[MAXSTRING];
char str5[MAXSTRING];
char str6[MAXSTRING];
doubleinstancestring(str1, *f, i, j, m, k);
tripleinstancestring(str3, *f, i, j, m, k, i, j);
tripleinstancestring(str4, *f, i, k, m, j, i, k);
quadinstancestring(str5, *f, i, j, m, k, i, j, m, k);
quadinstancestring(str6, *f, i, k, m, j, i, k, m, j);
if(m==i)
doubleinstancestring(str2, *f, i, k, m, j);
if(m==i && !nosubword(str1) && !nosubword(str2))
{ family copyf;
familyinit(©f);
copyfamily(©f, *f);
int newnumrepeats = 0;
for(int l=0; l<copyf.numrepeats[i]; l++)
{ if(l!=j)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][l];
}
copyf.numrepeats[i] = newnumrepeats;
addtolist(unsolved, copyf, 1);
#ifdef PRINTSPLIT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, copyf);
printf("%s and ", str);
#endif
clearfamily(©f);
familyinit(©f);
copyfamily(©f, *f);
newnumrepeats = 0;
for(int l=0; l<copyf.numrepeats[i]; l++)
{ if(l!=k)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][l];
}
copyf.numrepeats[i] = newnumrepeats;
addtolist(unsolved, copyf, 1);
#ifdef PRINTSPLIT
familystring(str, copyf);
printf("%s [because of %s, %s]\n", str, str1, str2);
#endif
clearfamily(©f);
return 1;
}
else if(m==i && iter>5 && (!nosubword(str1)))
{ family newf;
familyinit(&newf);
for(int l=0; l<f->len; l++)
{ char* newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, f->digit[l], newrepeats, f->numrepeats[l]);
if(i==l)
{ int newnumrepeats = 0;
int removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i+1][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+1] = newnumrepeats;
}
}
addtolist(unsolved, newf, 1);
#ifdef PRINTSPLIT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, newf);
printf("%s [because of %s]\n", str, str1);
#endif
clearfamily(&newf);
return 1;
}
else if(m==i && iter>5 && (!nosubword(str2)))
{ family newf;
familyinit(&newf);
for(int l=0; l<f->len; l++)
{ char* newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, f->digit[l], newrepeats, f->numrepeats[l]);
if(i==l)
{ int newnumrepeats = 0;
int removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i+1][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+1] = newnumrepeats;
}
}
addtolist(unsolved, newf, 1);
#ifdef PRINTSPLIT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, newf);
printf("%s [because of %s]\n", str, str2);
#endif
clearfamily(&newf);
return 1;
}
else if(m==i && iter>5 && (!nosubword(str3)))
{ family newf;
familyinit(&newf);
for(int l=0; l<f->len; l++)
{ char* newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, f->digit[l], newrepeats, f->numrepeats[l]);
if(i==l)
{ int newnumrepeats = 0;
int removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i+1][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+1] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i+2][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+2] = newnumrepeats;
}
}
addtolist(unsolved, newf, 1);
#ifdef PRINTSPLITEXT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, newf);
printf("%s [because of %s]\n", str, str3);
#endif
clearfamily(&newf);
return 1;
}
else if(m==i && iter>5 && (!nosubword(str4)))
{ family newf;
familyinit(&newf);
for(int l=0; l<f->len; l++)
{ char* newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, f->digit[l], newrepeats, f->numrepeats[l]);
if(i==l)
{ int newnumrepeats = 0;
int removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i+1][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+1] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i+2][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+2] = newnumrepeats;
}
}
addtolist(unsolved, newf, 1);
#ifdef PRINTSPLITEXT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, newf);
printf("%s [because of %s]\n", str, str4);
#endif
clearfamily(&newf);
return 1;
}
else if(m==i && iter>5 && (!nosubword(str5)))
{ family newf;
familyinit(&newf);
for(int l=0; l<f->len; l++)
{ char* newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, f->digit[l], newrepeats, f->numrepeats[l]);
if(i==l)
{ int newnumrepeats = 0;
int removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i+1][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+1] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i+2][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+2] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i+3][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+3] = newnumrepeats;
}
}
addtolist(unsolved, newf, 1);
#ifdef PRINTSPLITEXT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, newf);
printf("%s [because of %s]\n", str, str5);
#endif
clearfamily(&newf);
return 1;
}
else if(m==i && iter>5 && (!nosubword(str6)))
{ family newf;
familyinit(&newf);
for(int l=0; l<f->len; l++)
{ char* newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, f->digit[l], newrepeats, f->numrepeats[l]);
if(i==l)
{ int newnumrepeats = 0;
int removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i+1][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+1] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][k];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=k)
newf.repeats[i+2][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+2] = newnumrepeats;
newrepeats = malloc(f->numrepeats[l]*sizeof(char));
memcpy(newrepeats, f->repeats[l], f->numrepeats[l]*sizeof(char));
adddigit(&newf, 255, newrepeats, f->numrepeats[l]);
newnumrepeats = 0;
removeddigit = f->repeats[i][j];
for(int m=0; m<f->numrepeats[i]; m++)
{ if(m!=j)
newf.repeats[i+3][newnumrepeats++] = f->repeats[i][m];
}
newf.numrepeats[i+3] = newnumrepeats;
}
}
addtolist(unsolved, newf, 1);
#ifdef PRINTSPLITEXT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, newf);
printf("%s [because of %s]\n", str, str6);
#endif
clearfamily(&newf);
return 1;
}
else if(m>i && !nosubword(str1))
{ family copyf;
familyinit(©f);
copyfamily(©f, *f);
int newnumrepeats = 0;
for(int l=0; l<copyf.numrepeats[i]; l++)
{ if(l!=j)
copyf.repeats[i][newnumrepeats++] = copyf.repeats[i][l];
}
copyf.numrepeats[i] = newnumrepeats;
addtolist(unsolved, copyf, 1);
#ifdef PRINTSPLIT
char str[MAXSTRING];
familystring(str, *f);
printf("%s splits into ", str);
familystring(str, copyf);
printf("%s and ", str);
#endif
clearfamily(©f);
familyinit(©f);
copyfamily(©f, *f);
newnumrepeats = 0;
for(int l=0; l<copyf.numrepeats[m]; l++)
{ if(l!=k)
copyf.repeats[m][newnumrepeats++] = copyf.repeats[m][l];
}
copyf.numrepeats[m] = newnumrepeats;
addtolist(unsolved, copyf, 1);
#ifdef PRINTSPLIT
familystring(str, copyf);
printf("%s [because of %s]\n", str, str1);
#endif
clearfamily(©f);
return 1;
}
}
}
}
}
addtolist(unsolved, *f, insplit-1);
return 0;
}
void explore(family f, int side, int pos, list* unsolved)
{ int count = 0;
for(int i=0; i<f.len; i++)
if(f.numrepeats[i]>0)
count++;
pos = pos % count;
count = 0;
for(int i=0; i<f.len; i++)
{ if(f.numrepeats[i]>0)
{ if(pos==count)
{ char str[MAXSTRING];
familystring(str, f);
#ifdef PRINTEXPLORE
printf("exploring %s as ", str);
#endif
for(int j=0; j<f.numrepeats[i]; j++)
{ family newf;
familyinit(&newf);
instancefamily(&newf, f, side, i);
newf.digit[i+1] = f.repeats[i][j];
if(examine(&newf))
addtolist(unsolved, newf, 1);
#ifdef PRINTEXPLORE
familystring(str, newf);
printf("%s, ", str);
#endif
clearfamily(&newf);
}
family copyf;
familyinit(©f);
copyfamily(©f, f);
copyf.repeats[i] = NULL;
copyf.numrepeats[i] = 0;
if(examine(©f))
addtolist(unsolved, copyf, 1);
#ifdef PRINTEXPLORE
familystring(str, copyf);
printf("%s\n", str);
#endif
clearfamily(©f);
break;
}
count++;
}
}
}
int main(int argc, char** argv)
{ char filename[100];
sprintf(filename, "summary.txt");
FILE* summaryfile;
#ifdef CLEARSUMMARY
summaryfile = fopen(filename, "w");
fclose(summaryfile);
#endif
family f;
familyinit(&f);
int l, h, resume = 0;
if(argc==1)
{ printf("Computes minimal primes for bases between l and h,\n");
printf("possibly along with a set of unsolved families\n");
printf("Usage: ./minimal l h\n");
printf("To resume base b from iteration i: ./minimal resume b i\n");
return 0;
}
else if(strcmp(argv[1], "resume")==0)
{ l = h = atoi(argv[2]);
resume = 1;
iter = atoi(argv[3]);
}
else if(argc==2)
l = h = atoi(argv[1]);
else
{ l = atoi(argv[1]);
h = atoi(argv[2]);
}
#ifdef PRINTDATA
mkdir("data", S_IRWXU);
#endif
#ifdef PRINTITER
mkdir("iter", S_IRWXU);
#endif
for(base=l; base<=h; base++)
{
#ifdef PRINTSTATS
printf("base %d...\n", base);
#endif
kernelinit();
list unsolved;
listinit(&unsolved);
if(!resume)
{ for(int i=0; i<base; i++)
for(int j=0; j<base; j++)
for(int k=0; k<base; k++)
{ char str[4];
if(i==0 && j==0)
sprintf(str, "%c", digitchar(k));
else if(i==0)
sprintf(str, "%c%c", digitchar(j), digitchar(k));
else
sprintf(str, "%c%c%c", digitchar(i), digitchar(j), digitchar(k));
if(newminimal(str))
{ char* newstr = malloc(4);
memcpy(newstr, str, 4);
addtokernel(newstr);
}
}
for(int i=1; i<base; i++)
for(int j=0; j<base; j++)
{ char* middles = calloc(base, sizeof(char));
int middlesize = 0;
for(int k=0; k<base; k++)
{ char str[4];
sprintf(str, "%c%c%c", digitchar(i), digitchar(k), digitchar(j));
if(nosubword(str))
middles[middlesize++] = k;
}
if(middlesize>0)
{ family f;
familyinit(&f);
adddigit(&f, i, middles, middlesize);
adddigit(&f, j, NULL, 0);
if(!hasdivisor(f))
{ explore(f, 1, 0, &unsolved);
}
}
else
free(middles);
}
iter = 0;
}
else
{ char str[100];
sprintf(str, "iter/minimal-base%d-iter%d.txt", base, iter);
FILE* in = fopen(str, "r");
char line[MAXSTRING];
while(fgets(line, MAXSTRING, in)!=NULL)
{ line[strlen(line)-1] = '\0';
char* newstr = malloc(strlen(line)+1);
strcpy(newstr, line);
addtokernel(newstr);
#ifdef PRINTRESUME
printf("added %s to kernel\n", line);
#endif
}
fclose(in);
sprintf(str, "iter/unsolved-base%d-iter%d.txt", base, iter);
FILE* out = fopen(str, "r");
while(fgets(line, MAXSTRING, in)!=NULL)
{ family f;
familyinit(&f);
for(int i=0; i<strlen(line)-1; i++)
{ int digit;
if(line[i]=='{')
digit = 255;
else
digit = invdigitchar(line[i]);
if(line[i]!='{' && line[i+1]!='{')
{ adddigit(&f, digit, NULL, 0);
}
else
{ int k = strchr(line+i+1, '}')-(line+i+1)+(line[i]=='{'?1:0)-1;
char* middles = calloc(k, sizeof(char));
for(int j=i+2-(line[i]=='{'?1:0); j<k+i+2-(line[i]=='{'?1:0); j++)
{ middles[j-(i+2-(line[i]=='{'?1:0))] = invdigitchar(line[j]);
}
adddigit(&f, digit, middles, k);
i = k+i+2-(line[i]=='{'?1:0)+1;
}
}
addtolist(&unsolved, f, 2);
#ifdef PRINTRESUME
familystring(str, f);
printf("added %s to unknown list\n", str);
#endif
clearfamily(&f);
}
fclose(out);
iter++;
}
for(;; iter++)
{ if(!onlysimple(unsolved))
{ int didsplit = 1;
int splititer = 0;
while(didsplit)
{ didsplit = 0;
list oldlist;
copylist(&oldlist, unsolved);
clearlist(&unsolved);
for(int j=0; j<oldlist.size; j++)
didsplit |= split(&(oldlist.fam[j]), &unsolved, oldlist.split[j]);
clearlist(&oldlist);
removedupes(&unsolved);
copylist(&oldlist, unsolved);
clearlist(&unsolved);
for(int j=0; j<oldlist.size; j++)
if(oldlist.split[j]==0 || examine(&(oldlist.fam[j])))
addtolist(&unsolved, oldlist.fam[j], oldlist.split[j]);
clearlist(&oldlist);
removedupes(&unsolved);
copylist(&oldlist, unsolved);
clearlist(&unsolved);
for(int j=0; j<oldlist.size; j++)
didsplit |= split2(&(oldlist.fam[j]), &unsolved, oldlist.split[j]);
clearlist(&oldlist);
removedupes(&unsolved);
copylist(&oldlist, unsolved);
clearlist(&unsolved);
for(int j=0; j<oldlist.size; j++)
if(oldlist.split[j]==0 || examine(&(oldlist.fam[j])))
addtolist(&unsolved, oldlist.fam[j], oldlist.split[j]);
clearlist(&oldlist);
removedupes(&unsolved);
splititer++;
#ifdef PRINTSTATS
printf("base %d\titeration %d\tsplit %d\tsize %d\tremain %d\n", base, iter, splititer, K.size, unsolved.size);
#endif
}
}
else
break;
list oldlist;
copylist(&oldlist, unsolved);
clearlist(&unsolved);
for(int j=0; j<oldlist.size; j++)
explore(oldlist.fam[j], iter%2, iter, &unsolved);
clearlist(&oldlist);
removedupes(&unsolved);
#ifdef PRINTUNSOLVED
printf("Unsolved families after explore:\n");
printlist(unsolved);
#endif
#ifdef PRINTITER
char filename[100];
sprintf(filename, "iter/unsolved-base%d-iter%d.txt", base, iter);
FILE* out = fopen(filename, "w");
for(int j=0; j<unsolved.size; j++)
{ char str[MAXSTRING];
familystring(str, unsolved.fam[j]);
fprintf(out, "%s\n", str);
}
fclose(out);
filename[100];
sprintf(filename, "iter/minimal-base%d-iter%d.txt", base, iter);
out = fopen(filename, "w");
for(int j=0; j<K.size; j++)
{ fprintf(out, "%s\n", K.primes[j]);
}
fclose(out);
#endif
if(unsolved.size==0)
break;
}
kernel temp;
temp.size = 0;
temp.primes = NULL;
for(int i=0; i<K.size; i++)
if(nosubwordskip(K.primes[i], i))
{ int size = ++temp.size;
temp.primes = realloc(temp.primes, size*sizeof(char*));
temp.primes[size-1] = malloc(strlen(K.primes[i])+1);
strcpy(temp.primes[size-1], K.primes[i]);
}
clearkernel();
K = temp;
#ifdef PRINTDATA
sprintf(filename, "data/minimal.%d.txt", base);
FILE* kernelfile = fopen(filename, "w");
for(int i=0; i<K.size; i++)
fprintf(kernelfile, "%s\n", K.primes[i]);
fclose(kernelfile);
#endif
#ifdef PRINTSUMMARY
sprintf(filename, "summary.txt");
summaryfile = fopen(filename, "a");
fprintf(summaryfile, "BASE %d:\n", base);
fprintf(summaryfile, "\tSize:\t%d\n", K.size);
int width = strlen(K.primes[0]);
for(int i=1; i<K.size; i++)
if(width<strlen(K.primes[i]))
width = strlen(K.primes[i]);
fprintf(summaryfile, "\tWidth:\t%d\n", width);
fprintf(summaryfile, "\tRemain:\t%d\n", unsolved.size);
fclose(summaryfile);
#endif
#ifdef PRINTDATA
if(unsolved.size>0)
{ sprintf(filename, "data/unsolved.%d.txt", base);
FILE* unsolvedfile = fopen(filename, "w");
for(int i=0; i<unsolved.size; i++)
{ char str[MAXSTRING];
if(issimple(unsolved.fam[i]))
simplefamilystring(str, unsolved.fam[i]);
else
familystring(str, unsolved.fam[i]);
fprintf(unsolvedfile, "%s\n", str);
}
fclose(unsolvedfile);
}
#endif
clearkernel();
clearlist(&unsolved);
}
free(pr);
return 0;
}
Last fiddled with by sweety439 on 2022-04-30 at 23:00 |
|
|
|
![Reply](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="110" height="26"><rect fill-opacity="0"/></svg> "Reply") |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| generalized minimal (probable) primes | sweety439 | sweety439 | 140 | 2022-12-20 07:08 |
| Minimal set of the strings for primes with at least two digits | sweety439 | sweety439 | 6 | 2019-11-25 07:37 |
| Digit strings containing primes | davar55 | Puzzles | 13 | 2018-03-15 14:46 |
| Primes from powers of 2 strings. | Flatlander | Puzzles | 40 | 2011-02-10 09:42 |
| Strings of Digits | davar55 | Puzzles | 5 | 2008-11-02 00:08 |
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="11" height="7"><rect fill-opacity="0"/></svg>)
![View Post](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="12" height="12"><rect fill-opacity="0"/></svg> "View Post")