All the Primality Tests Inspired by an alphabet of 2 to , 3, letters and sets\ of forbidden words of size 1 where the words are constants and of lengt\ h from 2 to, 7 By Shalosh B. Ekhad 2 s - 3 [[{1, 2}, {[1, 1], [2, 2, 2]}], -----------, []] 3 2 s + s - 1 3 2 s + 2 s - 4 [[{1, 2}, {[1, 1], [2, 2, 2, 2]}], --------------------, [308, 1155, 49196]] 3 (s + 1) (s + s - 1) 4 3 2 s + 2 s + 3 s - 5 [[{1, 2}, {[1, 1], [2, 2, 2, 2, 2]}], ---------------------, 5 4 3 2 s + s + s + s - 1 [36, 40, 72, 289, 1404, 2808, 8964, 26244, 44712, 52488]] 5 4 3 2 s + 2 s + 3 s + 4 s - 6 [[{1, 2}, {[1, 1], [2, 2, 2, 2, 2, 2]}], ---------------------------, 5 3 (s + 1) (s + s + s - 1) [320, 10240, 13185, 16129, 17582]] 6 5 4 3 2 s + 2 s + 3 s + 4 s + 5 s - 7 [[{1, 2}, {[1, 1], [2, 2, 2, 2, 2, 2, 2]}], ----------------------------------, 7 6 5 4 3 2 s + s + s + s + s + s - 1 [36, 102, 6707, 9287, 68126, 93234]] 4 3 2 2 s + 4 s + 3 s - 5 [[{1, 2}, {[1, 1, 1], [2, 2, 2, 2]}], -------------------------, 5 4 3 2 s + 2 s + 2 s + s - 1 [49, 143, 190, 343, 836, 3721, 40670]] 5 4 3 2 2 s + 4 s + 6 s + 4 s - 6 [[{1, 2}, {[1, 1, 1], [2, 2, 2, 2, 2]}], --------------------------------, 6 5 4 3 2 s + 2 s + 2 s + 2 s + s - 1 [20, 636, 1062, 1134, 1470, 1582, 2146, 11367, 21546, 24398, 25330]] [[{1, 2}, {[1, 1, 1], [2, 2, 2, 2, 2, 2]}], 6 5 4 3 2 2 s + 4 s + 6 s + 8 s + 5 s - 7 ------------------------------------, [289, 4428, 18784, 19402, 21744]] 2 5 4 2 (s + s + 1) (s + s + s + s - 1) [[{1, 2}, {[1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], 7 6 5 4 3 2 2 s + 4 s + 6 s + 8 s + 10 s + 6 s - 8 ----------------------------------------------, 8 7 6 5 4 3 2 s + 2 s + 2 s + 2 s + 2 s + 2 s + s - 1 [20, 114, 187, 333, 351, 360, 1030, 1800, 2001, 35049, 57558, 87480, 93717] ] [[{1, 2}, {[1, 1, 1, 1], [2, 2, 2, 2, 2]}], 6 5 4 3 2 2 s + 6 s + 9 s + 8 s + 5 s - 7 ---------------------------------------, 7 6 5 4 3 2 s + 2 s + 3 s + 3 s + 2 s + s - 1 [25, 28, 66, 125, 3721, 6507, 25046, 52133]] [[{1, 2}, {[1, 1, 1, 1], [2, 2, 2, 2, 2, 2]}], 7 6 5 4 3 2 2 s + 6 s + 9 s + 12 s + 10 s + 6 s - 8 ---------------------------------------------, 7 6 5 4 3 (s + 1) (s + s + 2 s + s + 2 s + s - 1) [25, 121, 169, 196, 1104, 13836]] [[{1, 2}, {[1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], 8 7 6 5 4 3 2 2 s + 6 s + 9 s + 12 s + 15 s + 12 s + 7 s - 9 -----------------------------------------------------, 9 8 7 6 5 4 3 2 s + 2 s + 3 s + 3 s + 3 s + 3 s + 2 s + s - 1 [25, 49, 125, 143, 625, 3125, 14573, 14772, 15625]] [[{1, 2}, {[1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2]}], 8 7 6 5 4 3 2 2 s + 6 s + 12 s + 16 s + 15 s + 12 s + 7 s - 9 ------------------------------------------------------, [529, 16669, 53399] 9 8 7 6 5 4 3 2 s + 2 s + 3 s + 4 s + 4 s + 3 s + 2 s + s - 1 ] [[{1, 2}, {[1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], 9 8 7 6 5 4 3 2 2 s + 6 s + 12 s + 16 s + 20 s + 18 s + 14 s + 8 s - 10 ---------------------------------------------------------------, 10 9 8 7 6 5 4 3 2 s + 2 s + 3 s + 4 s + 4 s + 4 s + 3 s + 2 s + s - 1 [28, 154, 418, 792, 803, 1040, 1525, 1918, 13113, 76272]] [[{1, 2}, {[1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], 10 9 8 7 6 5 4 3 2 2 s + 6 s + 12 s + 20 s + 25 s + 24 s + 21 s + 16 s + 9 s - 11 ------------------------------------------------------------------------, 11 10 9 8 7 6 5 4 3 2 s + 2 s + 3 s + 4 s + 5 s + 5 s + 4 s + 3 s + 2 s + s - 1 [969, 1391, 1752, 1974, 3596, 5041, 6119, 43751]] 3 2 3 s + 6 s + 3 s - 4 [[{1, 2, 3}, {[1, 1], [2, 2, 2]}], ------------------------, [6, 9, 25, 4097]] 4 3 2 s + 3 s + 3 s + s - 1 4 3 2 3 s + 6 s + 9 s + 4 s - 5 [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2]}], ----------------------------------, 4 3 2 (s + 1) (s + 2 s + s + 2 s - 1) [6, 9, 12, 132, 708, 1053, 1073, 3771, 16627, 38809, 82308]] 5 4 3 2 3 s + 6 s + 9 s + 12 s + 5 s - 6 [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2, 2]}], --------------------------------------, 6 5 4 3 2 s + 3 s + 3 s + 3 s + 3 s + s - 1 [6, 9, 25, 125, 370, 6241, 17854, 63650]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2, 2, 2]}], 6 5 4 3 2 3 s + 6 s + 9 s + 12 s + 15 s + 6 s - 7 ----------------------------------------------, 6 5 4 3 2 (s + 1) (s + 2 s + s + 2 s + s + 2 s - 1) [6, 9, 18, 25, 125, 378, 1225, 3402, 10206, 30618]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2, 2, 2, 2]}], 7 6 5 4 3 2 3 s + 6 s + 9 s + 12 s + 15 s + 18 s + 7 s - 8 ----------------------------------------------------, 8 7 6 5 4 3 2 s + 3 s + 3 s + 3 s + 3 s + 3 s + 3 s + s - 1 [6, 9, 25, 12054, 13390, 39314, 52441]] 5 4 3 2 3 s + 10 s + 15 s + 12 s + 5 s - 6 [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2]}], --------------------------------------, 6 5 4 3 2 s + 3 s + 5 s + 5 s + 3 s + s - 1 [6, 25, 121, 169, 56454]] [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2, 2]}], 6 5 4 3 2 3 s + 10 s + 15 s + 20 s + 15 s + 6 s - 7 ----------------------------------------------, [6, 49, 1937, 27274, 59150] 7 6 5 4 3 2 s + 3 s + 5 s + 5 s + 5 s + 3 s + s - 1 ] [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2, 2, 2]}], 7 6 5 4 3 2 3 s + 10 s + 15 s + 20 s + 25 s + 18 s + 7 s - 8 ------------------------------------------------------, 2 6 5 4 3 2 (s + s + 1) (s + 2 s + 2 s + s + 2 s + 2 s - 1) [6, 170, 618, 1210, 6050, 12769, 30250, 42350, 52546]] [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], 8 7 6 5 4 3 2 3 s + 10 s + 15 s + 20 s + 25 s + 30 s + 21 s + 8 s - 9 --------------------------------------------------------------, 9 8 7 6 5 4 3 2 s + 3 s + 5 s + 5 s + 5 s + 5 s + 5 s + 3 s + s - 1 [6, 20, 60, 925, 1640, 4280, 34660, 51022, 85146]] [[{1, 2, 3}, {[1, 1, 1, 1], [2, 2, 2, 2, 2]}], 7 6 5 4 3 2 3 s + 10 s + 21 s + 28 s + 25 s + 18 s + 7 s - 8 ------------------------------------------------------, 8 7 6 5 4 3 2 s + 3 s + 5 s + 7 s + 7 s + 5 s + 3 s + s - 1 [6, 63, 189, 238, 678, 775, 3685]] [[{1, 2, 3}, {[1, 1, 1, 1], [2, 2, 2, 2, 2, 2]}], 8 7 6 5 4 3 2 3 s + 10 s + 21 s + 28 s + 35 s + 30 s + 21 s + 8 s - 9 --------------------------------------------------------------, 8 7 6 5 4 3 2 (s + 1) (s + 2 s + 3 s + 4 s + 3 s + 4 s + s + 2 s - 1) [6, 30, 511, 961, 1140, 4371, 19311, 64180]] [[{1, 2, 3}, {[1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], 9 8 7 6 5 4 3 2 3 s + 10 s + 21 s + 28 s + 35 s + 42 s + 35 s + 24 s + 9 s - 10 -----------------------------------------------------------------------, 10 9 8 7 6 5 4 3 2 s + 3 s + 5 s + 7 s + 7 s + 7 s + 7 s + 5 s + 3 s + s - 1 [6, 49, 70, 4489, 6813, 21655, 54023, 88777]] [[{1, 2, 3}, {[1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2]}], 9 8 7 6 5 4 3 2 3 s + 10 s + 21 s + 36 s + 45 s + 42 s + 35 s + 24 s + 9 s - 10 -----------------------------------------------------------------------, 10 9 8 7 6 5 4 3 2 s + 3 s + 5 s + 7 s + 9 s + 9 s + 7 s + 5 s + 3 s + s - 1 [6, 133, 738, 8138, 65302, 71003]] 10 9 8 [[{1, 2, 3}, {[1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], (3 s + 10 s + 21 s 7 6 5 4 3 2 / + 36 s + 45 s + 54 s + 49 s + 40 s + 27 s + 10 s - 11) / ( / 11 10 9 8 7 6 5 4 3 2 s + 3 s + 5 s + 7 s + 9 s + 9 s + 9 s + 7 s + 5 s + 3 s + s - 1 ), [6, 99, 102, 289, 294, 1849, 2442, 7070]] 11 10 [[{1, 2, 3}, {[1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2]}], (3 s + 10 s 9 8 7 6 5 4 3 2 + 21 s + 36 s + 55 s + 66 s + 63 s + 56 s + 45 s + 30 s + 11 s / 12 11 10 9 8 7 6 5 4 - 12) / (s + 3 s + 5 s + 7 s + 9 s + 11 s + 11 s + 9 s + 7 s / 3 2 + 5 s + 3 s + s - 1), [6, 90, 330, 1309, 10719, 11453]] The set of patterns with, followed by the generating function, with the leas\ t number of pseudoprimes less than, 100000, is: 2 s - 3 [[{1, 2}, {[1, 1], [2, 2, 2]}], -----------, []] 3 2 s + s - 1 --------------------- This took, 1004.421, seconds.