python | 100% faster without cheating (fully commented)
So there\'s definitely a lot that can be improved here, but it\'s late and I\'m not going to. There are a few tricks here I want to explain though. \n\nThe firs
So there\'s definitely a lot that can be improved here, but it\'s late and I\'m not going to. There are a few tricks here I want to explain though. \n\nThe first is that every palindromic number with an even length is a multiple of 11. This means that 11 is the only even-length palindromic prime. So rather than write code that can handle small values of N in general, I decided to write code that assumed that N > 11, and then I did use a lookup table for the smaller values. (The sample solutions for the top-speed all seem to use a lookup table which contains every prime palindrome less than 2*10^8, and then they lookup the answer with a binary search. So when I say I don\'t use a lookup table what I\'m really reffering to is that I didn\'t just do that)\n\nThe second trick I used is that I though of the palindromes as vectors, which I could write using linear combinations of easilly-constructible basis vectors. For example, the basis vectors for 5-digit palindromic numbers are:\n[10001, 01010, 00100] -> [10001, 1010, 100]\nWe can construct every 5-digit palindrome with a linear combination of these vectors. So if the digits of N are abcba, then we note that:\nN = a x 10001 + b x 1010 + c x 100\nTo be 5-digits, \'a\' cannot be 0. Furthermore, for \'N\' to have a chance of being prime, it must end with one of the digits (1, 3, 7, 9). This means that when we\'re generating palindromes which we want to be prime, we can restrict a to just those digits. (Notably, if the number \'abcba\' is greater than the number \'xyzyx\', then the number \'abc\' is greater than \'xyz\' and vice versa - this allowed me to easilly generate the palindromic numbers in ascending order)\n\nFinally, I did a little work to figure out lower bounds on where to start searching for palindromes. It\'s not perfect, but it\'s good enough to significantly reduce the computation time (mostly by not generating palindromes the same length as N that are way less than N).\n\n(also, I am fully aware that there\'s a lot of code here; this is not my most elegant solution ever, but beating a binary search of hard-coded answers was difficult)\n\nBest Performance: 28 ms/14.3 MB : 100%/32%\n\n\'\'\'\n\n    #Check if a Number is Prime (Trial Division - So this is definitely improvable)\n    def isPrime(self, n:int) -> bool:\n        #Check Edge Cases and Division by 2 and 3\n        if n == 2 or n == 3:\n            return True\n        elif n < 2 or n%2 == 0 or n%3 == 0:\n            return False\n        else:\n            #Check Division by Odd Numbers (6*k +/- 1)\n            return all(n%p != 0 != n%(p + 2) for p in range(5, int(n**0.5) + 1, 6))\n    \n    #Generate Prime Palindromes of Length D (d initially equals D)\n    def primePalindromes(self, D:int, d:int) -> int:\n        #Check the Base/Recursive Cases\n        if d == 1:\n            #If this is the Highest Level, Only Yield Primes\n            if D == 1:\n                #Yield Primes\n                yield from (p for p in [2,3,5,7])\n            else:\n                #Yield Every Digit\n                yield from range(10)\n        elif d == D:\n            #Compute the Basis Vector for this Level of the Recursion\n            v = 10**(d - 1) + 1\n            \n            #Since this is the Top Level, Only Check Candidate Primes\n            for n in (1, 3, 7, 9):\n                #Recursive Call\n                for p in self.primePalindromes(D, d - 2):\n                    #Assemble the Palindrome\n                    p = n*v + 10*p\n                    \n                    #Check if it\'s Prime\n                    if self.isPrime(p):\n                        #Yield the Prime Palindrome\n                        yield p\n        else:\n            #Compute the Basis Vector for this Level of the Recursion\n            v = 10**(d - 1) + 1\n            \n            #Try Every Digit\n            for n in range(10):\n                #Recursive Call\n                for p in self.primePalindromes(D, d - 2):\n                    #Assemble/Yield the Palindrome (This isn\'t the top level, so it isn\'t generally prime)\n                    yield n*v + 10*p\n    \n    #Generate Odd Palindromes the Same Length as N Which are Greater than N\n    def oddPalindromes(self, N:int) -> int:\n        #Cast N to a String for Easier Digit Manipulation\n        S = str(N)\n        \n        #Count the Number of Digits, and Compute the Number of Basis "Vectors" Required (Again, I know)\n        d = len(S)\n        D = d//2 + 1\n        \n        #Make the Basis Vectors (Ex: D = 5: basis = [10001, 01010, 00100])\n        basis = []\n        for i in range(D - 1):\n            basis.append(10**(d - i - 1) + 10**(i))\n        basis.append(10**(D - 1))\n        \n        #Yield Palindromes\n        for i in range(int(S[:D]), 10**D):\n            #Cast i to a String\n            s = str(i)\n            \n            #Add Leading Zeros\n            s = \'0\'*(D - len(s)) + s\n            \n            #Check if the Palindrome Might Be Prime\n            if s[0] in (\'1\', \'3\', \'7\', \'9\'):\n                #Assemble the Palindrome\n                p = sum(b*int(c) for b, c in zip(basis, s))\n                \n                #Check the Size\n                if p >= N:\n                    yield p\n    \n    #Solve the Puzzle\n    def primePalindrome(self, N: int) -> int:\n        #Check if N is Small (11 is Special Since All Even Palindromic Numbers are Multiples of 11)\n        if N < 12:\n            #Use a Lookup Table\n            return [2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11][N]\n        else:\n            #Generate Odd Palindromes Until the Solution is Either Found or Not Found\n            d = len(str(N))\n            if d%2 == 1:\n                for p in self.oddPalindromes(N):\n                    #Check if it\'s a Solution\n                    if self.isPrime(p):\n                        return p\n            else:\n                #Decrement d (So that it will be accurate when we increment it later)\n                d -= 1\n            \n            #Keep Generating Longer and Longer Prime Palindromes Until a Solution is Found\n            while True:\n                #Increment the Length of the Palindromes\n                d += 2\n                \n                #Generate Palindromes Greater than N\n                for p in self.primePalindromes(d, d):\n                    #Return the Solution\n                    return p\n\'\'\'\n\nAlso, for what it\'s worth, there\'s actually a slightly faster cheating solution. Instead of organizing all the primes in a single list, you can organize then in buckets based on the number of digits they have (plus a sentinel from the next bucket up). I didn\'t save a huge amount of time, but it\'s still significant since the solutions were already so quick to begin with! It is possible that this could be further improved by checking if N is odd and bigger than the biggest length-d solution before doing the binary search, but I doubt that\'d be enough to get the run time down to 20 ms, and I\'m not going to bother trying it.\n\nBest Performance: 24 ms/14.5 MB : 100%/14%\n\n\'\'\'\n\n\t#All the Solution Arranged by the Number of Digits\n    primes = {1:[2,3,5,7,11],\n              2:[11,101],\n              3:[101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301],\n              4:[10301],\n              5:[10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,\n                 15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,\n                 30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,\n                 36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,\n                 72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,\n                 78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,\n                 95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001],\n              6:[1003001],\n              7:[1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,\n                 1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,\n                 1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,\n                 1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,\n                 1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,\n                 1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,\n                 1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,\n                 1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,\n                 1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,\n                 1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,\n                 1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,\n                 1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,\n                 1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,\n                 1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,\n                 1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,\n                 1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,\n                 1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,\n                 1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,\n                 1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,\n                 3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,\n                 3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,\n                 3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,\n                 3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,\n                 3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,\n                 3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,\n                 3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,\n                 3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,\n                 3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,\n                 3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,\n                 3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,\n                 3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,\n                 3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,\n                 3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,\n                 3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,\n                 3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,\n                 3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,\n                 3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,\n                 7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,\n                 7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,\n                 7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,\n                 7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,\n                 7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,\n                 7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,\n                 7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,\n                 7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,\n                 7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,\n                 7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,\n                 7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,\n                 7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,\n                 7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,\n                 7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,\n                 7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,\n                 9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,\n                 9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,\n                 9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,\n                 9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,\n                 9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,\n                 9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,\n                 9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,\n                 9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,\n                 9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,\n                 9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,\n                 9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,\n                 9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,\n                 9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,\n                 9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,\n                 9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899,100030001],\n              8:[100030001],\n              9:[100030001]}\n    \n    #Solve the Puzzle\n    def primePalindrome(self, N: int) -> int:\n        #Get the Number of Digits\n        d = len(str(N))\n        \n        #Binary Search the Appropriate List\n        return self.primes[d][bisect_left(self.primes[d], N)]\n\'\'\'
['Python']