All the Finite Automata whose size is less than, 500, for determining the, CentralDellanoy, numbers modulo prime and prime powers for the first, 4, primes and powers <=, 3 By Shalosh B. Ekhad Recall that the, CentralDellanoy, numbers, let's call them A(n), may defined as the constant term of n (1/x + 3 + 2 x) We are interested in generating automata for computing super-fast A(n) modul\ o primes, and modulo prime powers allowing automata with at most, 500, states. for the first, 3, primes and as high powers as we can afford with our limit of, 500, states. Thanks to the Chinese Remainder Theorem, this would enable us to determine A\ (n) modulo many composite numbers as well. -------------------------------------- For A(n) modulo, 2, there is an automata with 1, states Here it is: [[[1, 1]], [1]] Just for fun, , A(100000000000000000000), modulo , 2, is , 1 and the next, 10, terms in the sequence A(n) modulo, 2, are 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 -------------------------------------- For A(n) modulo, 4, there is an automata with 8, states Here it is: [[[2, 3], [2, 4], [5, 6], [2, 7], [5, 8], [5, 6], [2, 7], [5, 6]], [1, 1, 3, 1, 3, 3, 1, 3]] Just for fun, , A(100000000000000000000), modulo , 4, is , 1 and the next, 10, terms in the sequence A(n) modulo, 4, are 3, 1, 3, 1, 3, 1, 3, 1, 3, 1 -------------------------------------- For A(n) modulo, 8, there is an automata with 54, states Here it is: [[[2, 3], [4, 5], [6, 7], [4, 8], [9, 10], [11, 12], [13, 14], [15, 16], [17, 18], [19, 20], [11, 21], [22, 23], [24, 25], [26, 27], [4, 28], [29, 30], [17, 31], [32, 33], [17, 18], [34, 35], [36, 37], [11, 12], [38, 39], [24, 40], [41, 42], [24, 25], [26, 27], [43, 44], [4, 28], [45, 46], [47, 48], [17, 18], [19, 20], [17, 18], [34, 35], [11, 12], [38, 39], [11, 12], [49, 50], [51, 52], [24, 25], [53, 54], [4, 28], [29, 30], [4, 28], [45, 46], [17, 18], [19, 20], [11, 12], [49, 50], [24, 25], [53, 54], [24, 25], [26, 27]], [1, 1, 3, 1, 5, 3, 7, 1 , 5, 5, 3, 3, 7, 7, 1, 1, 5, 5, 5, 5, 3, 3, 3, 7, 7, 7, 7, 1, 1, 1, 5, 5, 5, 5, 5, 3, 3, 3, 3, 7, 7, 7, 1, 1, 1, 1, 5, 5, 3, 3, 7, 7, 7, 7]] Just for fun, , A(100000000000000000000), modulo , 8, is , 1 and the next, 10, terms in the sequence A(n) modulo, 8, are 3, 5, 7, 1, 3, 5, 7, 1, 3, 5 -------------------------------------- For A(n) modulo, 3, there is an automata with 1, states Here it is: [[[1, 0, 1]], [1]] Just for fun, , A(100000000000000000000), modulo , 3, is , 0 and the next, 10, terms in the sequence A(n) modulo, 3, are 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 -------------------------------------- For A(n) modulo, 9, there is an automata with 18, states Here it is: [[[2, 3, 4], [2, 5, 6], [7, 8, 9], [10, 5, 11], [0, 12, 0], [13, 14, 6], [7, 0, 15], [12, 0, 16], [7, 0, 15], [10, 14, 17], [10, 5, 11], [12, 0, 16], [13, 18, 11], [0, 12, 0], [7, 0, 15], [12, 0, 16], [2, 18, 17], [0, 12, 0]], [1, 1, 3, 4 , 0, 7, 3, 6, 3, 4, 4, 6, 7, 0, 3, 6, 1, 0]] Just for fun, , A(100000000000000000000), modulo , 9, is , 0 and the next, 10, terms in the sequence A(n) modulo, 9, are 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 -------------------------------------- For A(n) modulo, 27, there is an automata with 240, states Here it is: [[[2, 3, 4], [5, 6, 7], [8, 9, 10], [11, 12, 13], [5, 14, 15], [16, 17, 18], [ 19, 20, 21], [22, 23, 24], [25, 26, 27], [28, 29, 30], [31, 32, 33], [34, 35, 18], [36, 37, 38], [39, 40, 41], [42, 43, 44], [45, 46, 47], [48, 49, 50], [51, 52, 53], [54, 55, 56], [57, 58, 59], [60, 61, 62], [22, 63, 64], [65, 66, 67], [68, 69, 70], [71, 72, 73], [74, 75, 76], [77, 78, 79], [80, 81, 82], [65, 66, 67], [83, 84, 85], [31, 86, 87], [88, 89, 59], [90, 91, 92], [45, 46, 47], [48, 49, 50], [93, 86, 94], [95, 96, 41], [97, 98, 99], [0, 100, 101], [102, 72, 103 ], [0, 104, 105], [106, 107, 108], [88, 109, 110], [111, 112, 113], [45, 114, 115], [116, 117, 118], [119, 120, 121], [102, 122, 123], [0, 124, 125], [126, 127, 128], [45, 114, 115], [116, 117, 118], [119, 120, 121], [54, 107, 129], [ 130, 131, 132], [133, 134, 135], [0, 100, 101], [71, 136, 123], [0, 137, 138], [139, 140, 129], [88, 109, 110], [60, 61, 62], [0, 141, 105], [142, 143, 144], [145, 146, 147], [148, 149, 150], [151, 152, 153], [154, 155, 156], [0, 104, 138], [142, 143, 144], [71, 72, 73], [0, 124, 125], [157, 158, 159], [145, 146, 147], [160, 161, 162], [163, 164, 165], [166, 136, 103], [0, 124, 125], [167, 168, 169], [80, 81, 82], [0, 104, 138], [170, 171, 172], [80, 81, 82], [0, 141, 105], [173, 174, 175], [176, 58, 110], [177, 178, 179], [0, 100, 101], [71, 136 , 123], [180, 181, 15], [182, 183, 132], [184, 185, 186], [93, 187, 33], [188, 189, 190], [0, 100, 101], [102, 72, 103], [93, 86, 94], [95, 96, 41], [97, 98, 99], [145, 146, 147], [0, 0, 0], [102, 122, 123], [126, 127, 128], [145, 146, 147], [0, 0, 0], [106, 140, 56], [191, 183, 192], [193, 194, 195], [71, 136, 123], [0, 137, 138], [54, 55, 56], [176, 89, 196], [111, 112, 113], [0, 0, 0], [197, 101, 198], [145, 146, 147], [0, 0, 0], [100, 199, 200], [45, 114, 115], [ 0, 0, 0], [197, 101, 198], [0, 201, 202], [167, 168, 169], [45, 114, 115], [0, 0, 0], [71, 72, 73], [0, 201, 202], [126, 127, 128], [203, 204, 205], [0, 100, 101], [166, 122, 73], [0, 141, 206], [93, 86, 94], [39, 207, 208], [209, 210, 211], [0, 212, 213], [145, 146, 147], [0, 0, 0], [139, 55, 108], [182, 214, 215 ], [145, 146, 147], [154, 155, 156], [0, 104, 138], [142, 143, 144], [145, 146, 147], [0, 0, 0], [100, 199, 200], [145, 146, 147], [0, 0, 0], [100, 199, 200], [145, 146, 147], [0, 0, 0], [100, 199, 200], [154, 155, 156], [0, 137, 206], [ 173, 174, 175], [102, 122, 123], [0, 212, 213], [157, 158, 159], [45, 114, 115] , [0, 0, 0], [197, 101, 198], [145, 146, 147], [0, 0, 0], [100, 199, 200], [166 , 136, 103], [166, 136, 103], [0, 124, 125], [167, 168, 169], [22, 63, 64], [0, 137, 206], [170, 171, 172], [80, 81, 82], [0, 141, 105], [173, 174, 175], [0, 100, 101], [216, 14, 217], [191, 131, 215], [218, 219, 220], [180, 221, 217], [ 222, 96, 208], [0, 100, 101], [166, 122, 73], [216, 14, 217], [130, 214, 192], [184, 185, 186], [57, 109, 196], [5, 221, 223], [130, 214, 192], [224, 225, 226 ], [0, 100, 101], [0, 141, 206], [227, 187, 87], [222, 40, 228], [97, 98, 99], [0, 137, 138], [45, 114, 115], [197, 101, 198], [0, 0, 0], [100, 199, 200], [45 , 114, 115], [0, 0, 0], [31, 32, 33], [95, 96, 41], [229, 230, 231], [0, 0, 0], [102, 72, 103], [0, 104, 105], [31, 32, 33], [222, 40, 228], [209, 210, 211], [ 45, 114, 115], [0, 0, 0], [166, 122, 73], [0, 141, 206], [216, 181, 223], [232, 233, 234], [5, 221, 223], [182, 183, 132], [218, 219, 220], [95, 207, 228], [0, 100, 101], [235, 236, 237], [180, 181, 15], [191, 131, 215], [224, 225, 226], [ 227, 32, 94], [0, 104, 105], [227, 187, 87], [39, 207, 208], [229, 230, 231], [ 54, 55, 56], [57, 58, 59], [60, 61, 62], [139, 140, 129], [176, 89, 196], [238, 239, 240], [106, 107, 108], [57, 58, 59], [238, 239, 240]], [1, 1, 3, 13, 1, 9, 25, 3, 24, 12, 13, 9, 22, 0, 7, 9, 6, 9, 25, 0, 16, 3, 18, 21, 24, 18, 15, 12, 18, 12, 13, 0, 19, 9, 6, 22, 0, 22, 0, 6, 0, 7, 0, 25, 9, 18, 9, 6, 0, 24, 9, 18, 9, 25, 0, 22, 0, 24, 0, 16, 0, 16, 0, 21, 18, 18, 18, 21, 0, 21, 24, 0, 6, 18, 9, 18, 15, 0, 15, 12, 0, 3, 12, 0, 12, 0, 10, 0, 24, 19, 0, 10, 22, 1, 0, 6 , 22, 0, 22, 18, 0, 6, 24, 18, 0, 7, 0, 4, 24, 0, 25, 0, 25, 0, 9, 18, 0, 18, 9 , 0, 9, 0, 15, 9, 0, 24, 0, 24, 13, 0, 15, 0, 22, 0, 13, 0, 18, 0, 16, 0, 18, 21, 0, 21, 18, 0, 18, 18, 0, 18, 18, 0, 18, 21, 0, 12, 6, 0, 6, 9, 0, 9, 18, 0, 18, 15, 15, 0, 15, 3, 0, 3, 12, 0, 12, 0, 10, 0, 1, 19, 0, 0, 15, 10, 0, 10, 0, 1, 0, 19, 0, 0, 4, 0, 22, 0, 9, 9, 0, 18, 9, 0, 13, 0, 4, 0, 6, 0, 13, 0, 13, 9 , 0, 15, 0, 10, 25, 1, 0, 1, 0, 0, 16, 19, 0, 19, 4, 0, 4, 0, 4, 25, 0, 16, 16, 0, 7, 7, 0, 7]] Just for fun, , A(100000000000000000000), modulo , 27, is , 0 and the next, 10, terms in the sequence A(n) modulo, 27, are 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 -------------------------------------- For A(n) modulo, 5, there is an automata with 4, states Here it is: [[[1, 2, 2, 2, 1], [2, 3, 3, 3, 2], [3, 4, 4, 4, 3], [4, 1, 1, 1, 4]], [1, 3, 4 , 2]] Just for fun, , A(100000000000000000000), modulo , 5, is , 2 and the next, 10, terms in the sequence A(n) modulo, 5, are 1, 1, 1, 2, 1, 3, 3, 3, 1, 1 -------------------------------------- For A(n) modulo, 25, there is an automata with 265, states Here it is: [[[2, 3, 4, 5, 6], [2, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20] , [16, 21, 13, 23, 22], [24, 25, 8, 26, 27], [28, 21, 29, 31, 30], [11, 32, 33, 34, 35], [36, 37, 38, 31, 15], [39, 40, 41, 42, 10], [11, 43, 44, 45, 46], [47, 48, 49, 50, 51], [52, 53, 54, 55, 56], [57, 58, 59, 50, 60], [36, 61, 62, 63, 46], [16, 64, 62, 65, 66], [47, 48, 49, 50, 51], [52, 53, 54, 55, 56], [52, 67, 49, 69, 68], [36, 61, 62, 63, 46], [70, 67, 59, 71, 72], [16, 73, 44, 74, 75], [52, 67, 49, 69, 68], [24, 76, 41, 77, 78], [16, 79, 38, 81, 80], [82, 79, 29, 14, 83], [24, 25, 8, 26, 27], [28, 73, 84, 63, 85], [57, 86, 87, 88, 89], [11, 90, 91, 65, 85], [92, 93, 94, 71, 51], [57, 93, 95, 96, 68], [47, 97, 98, 99, 100], [47, 101, 95, 102, 72], [16, 73, 44, 74, 75], [36, 90, 103, 74, 104], [57 , 93, 95, 96, 68], [92, 105, 106, 107, 108], [39, 109, 110, 26, 111], [36, 112, 113, 23, 83], [16, 17, 18, 19, 20], [11, 112, 114, 81, 30], [92, 101, 115, 69, 60], [57, 86, 87, 88, 89], [52, 67, 49, 69, 68], [36, 61, 62, 63, 46], [47, 116 , 117, 118, 119], [120, 121, 122, 124, 123], [125, 126, 127, 128, 129], [130, 131, 132, 124, 133], [92, 134, 135, 136, 119], [52, 137, 135, 138, 139], [120, 121, 122, 124, 123], [125, 126, 127, 128, 129], [125, 140, 122, 141, 142], [92, 134, 135, 136, 119], [57, 134, 143, 144, 145], [125, 131, 146, 148, 147], [130, 149, 150, 151, 152], [57, 137, 153, 118, 154], [52, 58, 94, 102, 155], [47, 97, 98, 99, 100], [57, 58, 59, 50, 60], [70, 67, 59, 71, 72], [92, 93, 94, 71, 51], [28, 43, 103, 156, 66], [157, 140, 132, 158, 159], [52, 160, 117, 161, 145], [ 125, 140, 122, 141, 142], [70, 160, 153, 136, 162], [163, 164, 146, 158, 123], [47, 165, 143, 138, 162], [47, 48, 49, 50, 51], [70, 48, 115, 96, 155], [16, 73 , 44, 74, 75], [82, 37, 114, 166, 22], [28, 12, 113, 166, 80], [167, 7, 110, 168, 78], [52, 58, 94, 102, 155], [28, 43, 103, 156, 66], [47, 101, 95, 102, 72 ], [82, 61, 91, 156, 75], [82, 64, 84, 45, 104], [92, 105, 106, 107, 108], [11, 90, 91, 65, 85], [157, 140, 132, 158, 159], [130, 149, 150, 151, 152], [130, 131, 132, 124, 133], [47, 165, 143, 138, 162], [57, 93, 95, 96, 68], [70, 169, 170, 171, 172], [92, 165, 173, 161, 154], [130, 164, 174, 175, 142], [163, 176, 177, 178, 179], [120, 180, 181, 182, 183], [157, 121, 184, 175, 147], [130, 164 , 174, 175, 142], [120, 180, 181, 182, 183], [120, 185, 174, 148, 159], [52, 160, 117, 161, 145], [163, 185, 184, 141, 133], [120, 185, 174, 148, 159], [52, 53, 54, 55, 56], [82, 64, 84, 45, 104], [125, 131, 146, 148, 147], [163, 176, 177, 178, 179], [163, 164, 146, 158, 123], [70, 116, 173, 144, 139], [11, 12, 13, 14, 15], [36, 186, 187, 188, 189], [190, 76, 191, 9, 111], [92, 101, 115, 69, 60], [70, 169, 170, 171, 172], [47, 97, 98, 99, 100], [157, 192, 193, 194, 195], [163, 185, 184, 141, 133], [130, 149, 150, 151, 152], [125, 140, 122, 141 , 142], [92, 134, 135, 136, 119], [120, 196, 197, 198, 199], [39, 200, 201, 203 , 202], [167, 204, 205, 206, 207], [163, 208, 209, 210, 199], [24, 211, 212, 203, 213], [125, 214, 209, 215, 216], [39, 200, 201, 203, 202], [167, 204, 205, 206, 207], [167, 217, 201, 219, 218], [163, 208, 209, 210, 199], [130, 208, 220 , 221, 222], [167, 211, 223, 225, 224], [24, 226, 227, 228, 229], [130, 214, 230, 198, 231], [125, 131, 146, 148, 147], [120, 180, 181, 182, 183], [130, 131 , 132, 124, 133], [157, 140, 132, 158, 159], [163, 164, 146, 158, 123], [70, 116, 173, 144, 139], [2, 217, 212, 232, 233], [167, 217, 201, 219, 218], [125, 234, 197, 235, 222], [157, 192, 193, 194, 195], [120, 185, 174, 148, 159], [52, 160, 117, 161, 145], [190, 236, 237, 238, 239], [157, 196, 240, 221, 216], [39, 241, 242, 225, 233], [2, 217, 212, 232, 233], [24, 226, 227, 228, 229], [24, 211, 212, 203, 213], [120, 243, 220, 215, 244], [163, 176, 177, 178, 179], [57, 137, 153, 118, 154], [70, 116, 173, 144, 139], [47, 101, 95, 102, 72], [157, 234, 230, 210, 244], [190, 245, 223, 232, 202], [120, 243, 220, 215, 244], [120 , 121, 122, 124, 123], [157, 121, 184, 175, 147], [47, 165, 143, 138, 162], [ 163, 243, 240, 235, 231], [24, 245, 242, 246, 218], [130, 164, 174, 175, 142], [70, 48, 115, 96, 155], [167, 25, 191, 42, 247], [16, 21, 13, 23, 22], [163, 185, 184, 141, 133], [157, 192, 193, 194, 195], [157, 121, 184, 175, 147], [57, 137, 153, 118, 154], [125, 126, 127, 128, 129], [39, 248, 249, 250, 251], [2, 200, 252, 246, 224], [167, 211, 223, 225, 224], [190, 236, 237, 238, 239], [190 , 245, 223, 232, 202], [157, 196, 240, 221, 216], [24, 245, 242, 246, 218], [39 , 248, 249, 250, 251], [39, 241, 242, 225, 233], [125, 234, 197, 235, 222], [2, 253, 254, 255, 256], [190, 241, 252, 219, 213], [52, 58, 94, 102, 155], [92, 105, 106, 107, 108], [92, 93, 94, 71, 51], [28, 43, 103, 156, 66], [190, 40, 257, 168, 27], [28, 258, 259, 260, 261], [190, 241, 252, 219, 213], [2, 253, 254, 255, 256], [2, 200, 252, 246, 224], [130, 214, 230, 198, 231], [190, 241, 252, 219, 213], [24, 226, 227, 228, 229], [167, 217, 201, 219, 218], [163, 208, 209, 210, 199], [28, 21, 29, 31, 30], [82, 262, 263, 264, 265], [190, 76, 191, 9, 111], [36, 37, 38, 31, 15], [28, 21, 29, 31, 30], [82, 262, 263, 264, 265], [82, 79, 29, 14, 83], [190, 76, 191, 9, 111], [167, 211, 223, 225, 224], [39, 248, 249, 250, 251], [24, 211, 212, 203, 213], [82, 37, 114, 166, 22], [36, 186 , 187, 188, 189], [24, 25, 8, 26, 27], [2, 217, 212, 232, 233], [190, 245, 223, 232, 202], [157, 196, 240, 221, 216], [16, 79, 38, 81, 80], [167, 7, 110, 168, 78], [82, 79, 29, 14, 83], [2, 253, 254, 255, 256], [39, 241, 242, 225, 233], [ 125, 234, 197, 235, 222], [11, 32, 33, 34, 35], [2, 109, 257, 77, 247], [28, 12 , 113, 166, 80], [16, 79, 38, 81, 80], [36, 186, 187, 188, 189], [36, 37, 38, 31, 15], [39, 40, 41, 42, 10], [190, 236, 237, 238, 239], [130, 214, 230, 198, 231], [11, 112, 114, 81, 30], [39, 40, 41, 42, 10], [39, 200, 201, 203, 202], [ 2, 200, 252, 246, 224], [82, 37, 114, 166, 22], [11, 32, 33, 34, 35], [11, 112, 114, 81, 30], [2, 109, 257, 77, 247], [167, 204, 205, 206, 207], [11, 12, 13, 14, 15], [28, 258, 259, 260, 261], [24, 245, 242, 246, 218], [120, 243, 220, 215, 244], [36, 112, 113, 23, 83], [16, 21, 13, 23, 22], [2, 109, 257, 77, 247] , [36, 112, 113, 23, 83], [28, 258, 259, 260, 261], [28, 12, 113, 166, 80], [ 167, 7, 110, 168, 78], [16, 17, 18, 19, 20], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [16, 21, 13, 23, 22], [24, 25, 8, 26, 27], [82, 262, 263, 264, 265], [ 92, 101, 115, 69, 60], [70, 169, 170, 171, 172], [70, 48, 115, 96, 155], [82, 64, 84, 45, 104], [70, 67, 59, 71, 72], [57, 86, 87, 88, 89], [57, 58, 59, 50, 60], [11, 90, 91, 65, 85]], [1, 1, 3, 13, 13, 21, 8, 3, 23, 16, 3, 14, 19, 9, 23, 13, 14, 19, 19, 23, 4, 13, 19, 21, 13, 18, 21, 8, 9, 3, 24, 9, 14, 14, 13, 23, 9, 24, 16, 23, 13, 3, 24, 9, 19, 23, 14, 7, 22, 17, 24, 19, 7, 22, 22, 24, 9, 22, 17, 9, 19, 14, 9, 4, 24, 8, 2, 19, 22, 4, 12, 14, 14, 4, 13, 18, 8, 11, 19, 8, 14, 18, 18, 24, 3, 2, 17, 17, 14, 9, 4, 24, 17, 12, 7, 2, 17, 7, 7, 19, 12, 7, 19, 18, 22, 12, 12, 4, 3, 23, 6, 24, 4, 14, 2, 12, 17, 22, 24, 7, 16, 11 , 12, 21, 22, 16, 11, 11, 12, 17, 11, 21, 17, 22, 7, 17, 2, 12, 4, 1, 11, 22, 2 , 7, 19, 6, 2, 16, 1, 21, 21, 7, 12, 9, 4, 14, 2, 6, 7, 7, 2, 14, 12, 21, 17, 4 , 11, 13, 12, 2, 2, 9, 22, 16, 1, 11, 6, 6, 2, 21, 16, 16, 22, 1, 6, 19, 24, 24 , 8, 6, 8, 6, 1, 1, 17, 6, 21, 11, 12, 8, 18, 6, 23, 8, 18, 18, 6, 11, 16, 21, 18, 23, 21, 1, 6, 2, 13, 11, 18, 1, 16, 22, 3, 1, 8, 13, 23, 23, 16, 6, 17, 3, 16, 16, 1, 18, 3, 3, 1, 11, 3, 8, 21, 7, 23, 13, 1, 23, 8, 8, 11, 13, 3, 13, 13 , 21, 18, 24, 4, 4, 18, 4, 9, 9, 3]] Just for fun, , A(100000000000000000000), modulo , 25, is , 22 and the next, 10, terms in the sequence A(n) modulo, 25, are 16, 11, 11, 12, 1, 8, 8, 13, 11, 16 -------------------------------------- For A(n) modulo, 7, there is an automata with 6, states Here it is: [[[1, 2, 3, 0, 3, 2, 1], [2, 4, 5, 0, 5, 4, 2], [3, 5, 1, 0, 1, 5, 3], [4, 3, 6 , 0, 6, 3, 4], [5, 6, 2, 0, 2, 6, 5], [6, 1, 4, 0, 4, 1, 6]], [1, 3, 6, 2, 4, 5 ]] Just for fun, , A(100000000000000000000), modulo , 7, is , 0 and the next, 10, terms in the sequence A(n) modulo, 7, are 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ------------------------------------------------ This ends this thrilling article, that took, 9.021, seconds. to produce .