All the Primality Tests Inspired by an alphabet of 3, letters and sets\ of forbidden words of size 3 where the words are constants and of lengt\ h from 2 to, 7 By Shalosh B. Ekhad [[{1, 2, 3}, {[1, 1], [2, 2, 2], [3, 3, 3, 3]}], 5 4 3 2 5 s + 14 s + 18 s + 12 s - 6 -------------------------------------------, [6, 9]] 5 4 3 2 (s + 1) (2 s + 3 s + 4 s + 2 s + s - 1) [[{1, 2, 3}, {[1, 1], [2, 2, 2], [3, 3, 3, 3, 3]}], 6 5 4 3 2 5 s + 14 s + 21 s + 24 s + 15 s - 7 -------------------------------------------, 7 6 5 4 3 2 2 s + 5 s + 7 s + 7 s + 6 s + 3 s - 1 [6, 9, 25, 49, 125, 310, 318, 4873, 16854, 27759, 68910]] [[{1, 2, 3}, {[1, 1], [2, 2, 2], [3, 3, 3, 3, 3, 3]}], 7 6 5 4 3 2 5 s + 14 s + 21 s + 28 s + 30 s + 18 s - 8 -----------------------------------------------------, 3 2 5 4 3 2 (s + 2 s + 2 s + 1) (2 s + s + s + s + 2 s - 1) [6, 9, 25, 66, 125, 225, 1179, 23422, 55395]] [[{1, 2, 3}, {[1, 1], [2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], 8 7 6 5 4 3 2 5 s + 14 s + 21 s + 28 s + 35 s + 36 s + 21 s - 9 ---------------------------------------------------------, 9 8 7 6 5 4 3 2 2 s + 5 s + 7 s + 7 s + 7 s + 7 s + 6 s + 3 s - 1 [6, 9, 25, 27, 30, 444, 1681, 6773, 7964, 12988, 17161]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2], [3, 3, 3, 3, 3]}], 7 6 5 4 3 2 5 s + 16 s + 30 s + 36 s + 30 s + 18 s - 8 ---------------------------------------------------------, 7 6 5 4 3 2 (s + 1) (2 s + 3 s + 5 s + 5 s + 4 s + 2 s + s - 1) [6, 9, 12, 27, 77, 169, 2532, 5889, 8149, 11823, 45106]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2], [3, 3, 3, 3, 3, 3]}], 7 6 5 4 3 2 5 s + 11 s + 19 s + 21 s + 24 s + 12 s + 9 s - 9 ------------------------------------------------------, 7 6 5 4 3 (s + 1) (2 s + s + 4 s + s + 4 s + 2 s - 1) [6, 9, 12, 56, 588, 11118, 11480, 12191, 18582]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], 9 8 7 6 5 4 3 2 5 s + 16 s + 30 s + 40 s + 50 s + 54 s + 42 s + 24 s - 10 -----------------------------------------------------------------------, 9 8 7 6 5 4 3 2 (s + 1) (2 s + 3 s + 5 s + 5 s + 5 s + 5 s + 4 s + 2 s + s - 1) [6, 9, 12, 154, 252, 434, 494, 1479, 13459, 17557]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3]}], 9 8 7 6 5 4 3 2 5 s + 16 s + 33 s + 52 s + 60 s + 54 s + 42 s + 24 s - 10 -----------------------------------------------------------------------, [ 9 8 7 6 5 4 3 2 (s + 1) (2 s + 3 s + 5 s + 6 s + 7 s + 5 s + 4 s + 2 s + s - 1) 6, 9, 25, 45, 125, 266, 312, 625, 1645, 1681, 2050, 3125, 5370, 18657, 30673, 70614]] [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], ( 10 9 8 7 6 5 4 3 2 5 s + 16 s + 33 s + 52 s + 65 s + 72 s + 63 s + 48 s + 27 s - 11) / 11 10 9 8 7 6 5 4 3 / (2 s + 5 s + 8 s + 11 s + 13 s + 13 s + 12 s + 9 s + 6 s / 2 + 3 s - 1), [6, 9, 25, 3560, 3945, 6851, 11881, 15495, 52180]] 11 [[{1, 2, 3}, {[1, 1], [2, 2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], (5 s 10 9 8 7 6 5 4 3 2 + 16 s + 33 s + 56 s + 80 s + 90 s + 84 s + 72 s + 54 s + 30 s / 11 10 9 8 7 6 5 - 12) / ((s + 1) (2 s + 3 s + 5 s + 6 s + 8 s + 8 s + 7 s / 4 3 2 + 5 s + 4 s + 2 s + s - 1)), [6, 9, 25, 670, 852, 6625, 49932, 66254]] [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3, 3]}], 8 7 6 5 4 3 2 6 s + 22 s + 45 s + 64 s + 65 s + 48 s + 21 s - 9 -------------------------------------------------------------, 9 8 7 6 5 4 3 2 2 s + 6 s + 11 s + 15 s + 16 s + 13 s + 8 s + 3 s - 1 [6, 25, 125, 196, 289, 2752, 9994, 17219, 18968]] [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3, 3, 3]}], 9 8 7 6 5 4 3 2 6 s + 22 s + 45 s + 68 s + 80 s + 78 s + 56 s + 24 s - 10 -----------------------------------------------------------------------, 3 2 7 6 5 4 3 2 (s + 2 s + 2 s + 1) (2 s + 2 s + 3 s + 3 s + 3 s + s + 2 s - 1) [6, 20, 25, 40, 196, 306, 798, 7921, 37944, 81679]] [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], ( 10 9 8 7 6 5 4 3 2 6 s + 22 s + 45 s + 68 s + 85 s + 96 s + 91 s + 64 s + 27 s - 11) / 11 10 9 8 7 6 5 4 3 / (2 s + 6 s + 11 s + 15 s + 17 s + 17 s + 16 s + 13 s + 8 s / 2 + 3 s - 1), [6, 20, 25, 80, 289, 1687, 1990, 2990, 4125, 21867, 57011, 58581, 60451, 83355]] 10 9 [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3]}], (6 s + 22 s 8 7 6 5 4 3 2 / + 48 s + 80 s + 105 s + 108 s + 91 s + 64 s + 27 s - 11) / ( / 2 (s + s + 1) 9 8 7 6 5 4 3 2 (2 s + 4 s + 5 s + 7 s + 8 s + 6 s + 4 s + 3 s + s - 1)), [6, 35, 560, 2264, 2685, 3157, 8877, 18769]] 11 [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], (6 s 10 9 8 7 6 5 4 3 + 22 s + 48 s + 80 s + 110 s + 126 s + 126 s + 104 s + 72 s 2 / 12 11 10 9 8 7 6 + 30 s - 12) / (2 s + 6 s + 11 s + 16 s + 20 s + 22 s + 21 s / 5 4 3 2 + 18 s + 13 s + 8 s + 3 s - 1), [6, 20, 49, 88, 532, 639, 2209, 2501, 3354, 6940, 27110, 50928]] 12 [[{1, 2, 3}, {[1, 1, 1], [2, 2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], (6 s 11 10 9 8 7 6 5 4 + 22 s + 48 s + 84 s + 125 s + 156 s + 161 s + 144 s + 117 s 3 2 / 2 11 10 9 8 + 80 s + 33 s - 13) / ((s + s + 1) (2 s + 4 s + 5 s + 7 s / 7 6 5 4 3 2 + 9 s + 9 s + 8 s + 6 s + 4 s + 3 s + s - 1)), [6, 20, 88, 100, 160, 176, 240, 352, 944, 1504, 3504, 3856, 3965, 10591, 60009]] 11 [[{1, 2, 3}, {[1, 1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3]}], (6 s 10 9 8 7 6 5 4 3 + 24 s + 57 s + 100 s + 140 s + 162 s + 154 s + 120 s + 72 s 2 / 11 10 9 8 7 6 + 30 s - 12) / ((s + 1) (2 s + 4 s + 8 s + 11 s + 14 s + 14 s / 5 4 3 2 + 13 s + 9 s + 6 s + 2 s + s - 1)), [6, 184, 703, 2418, 17149, 20538, 35927]] 12 [[{1, 2, 3}, {[1, 1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], (6 s 11 10 9 8 7 6 5 4 + 24 s + 57 s + 100 s + 145 s + 180 s + 189 s + 176 s + 135 s 3 2 / 13 12 11 10 9 8 + 80 s + 33 s - 13) / (2 s + 6 s + 12 s + 19 s + 25 s + 29 s / 7 6 5 4 3 2 + 30 s + 27 s + 22 s + 15 s + 8 s + 3 s - 1), [6, 121, 152, 240, 1331, 3363, 4152, 14641, 17161]] 13 [[{1, 2, 3}, {[1, 1, 1, 1], [2, 2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], (6 s 12 11 10 9 8 7 6 5 + 24 s + 57 s + 104 s + 160 s + 210 s + 238 s + 232 s + 198 s 4 3 2 / 13 12 11 + 150 s + 88 s + 36 s - 14) / ((s + 1) (2 s + 4 s + 8 s / 10 9 8 7 6 5 4 3 2 + 11 s + 15 s + 17 s + 18 s + 16 s + 13 s + 9 s + 6 s + 2 s + s - 1)), [6, 30, 3464, 13482, 27227, 90029, 91549]] [[{1, 2, 3}, {[1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3, 3]}], ( 14 13 12 11 10 9 8 7 6 s + 24 s + 60 s + 116 s + 185 s + 252 s + 301 s + 320 s 6 5 4 3 2 / 15 14 + 297 s + 240 s + 165 s + 96 s + 39 s - 15) / (2 s + 6 s / 13 12 11 10 9 8 7 6 + 12 s + 20 s + 29 s + 37 s + 42 s + 43 s + 40 s + 33 s 5 4 3 2 + 24 s + 15 s + 8 s + 3 s - 1), [6, 361, 1369, 1681, 1855, 2321, 4557, 7270, 28467, 47082, 86870, 90802]] The set of patterns with, followed by the generating function, with the leas\ t number of pseudoprimes less than, 100000, is: [[{1, 2, 3}, {[1, 1], [2, 2, 2], [3, 3, 3, 3]}], 5 4 3 2 5 s + 14 s + 18 s + 12 s - 6 -------------------------------------------, [6, 9]] 5 4 3 2 (s + 1) (2 s + 3 s + 4 s + 2 s + s - 1) --------------------- This took, 6404.606, seconds.