# Shortest code to find next prime palindrome

I was trying to find the shortest code possible that given a number n, returns the next prime palindrome number (limited to below 100000). If the number itself is a prime palindrome, the code should return the next one.

Write the shortest program/function that, when given an input n (less than 100000), returns the next palindromic prime number.

This is an example working program:

def golf(n):
n+=1
while str(n)!=str(n)[::-1] or not all(n%i for i in xrange(2,n)):n+=1
return n
• This seems more like a general request which are meant for Stack Overflow. This site is more of a programming contest. But I can easily see this as a contest, give you remove the limitation of Python language and add the code-golf tag Sep 27, 2014 at 18:34
• Do you copy ???? Sep 27, 2014 at 18:43
• I edited your question to make it into a valid contest here. If you really just wanted to know how to shorten your code, that is not for this site. Sep 27, 2014 at 19:06
• Can we assume that n is a positive integer? Sep 28, 2014 at 4:53
• yes you can assume that Sep 28, 2014 at 8:49

# CJam, 15 bytes

li{)__mfsW%i^}g

Reads a single, positive integer from STDIN. Try it online.

$cjam <(echo 'li{)__mfsW%i^}g') <<< 250 313 ### How it works This uses a tricky prime check instead of the built-in mp: 15 mf, for example, pushes [3 5]. We cast to a string ("35"), reverse that string ("53"), cast to integer (53) and XOR the result with the original integer (22). Since the result in non-zero, 35 is not a palindromic prime. li " N := int(input()) "; { }g " While R: "; ) " N += 1 "; _mfs " R := str(factorize(N)) "; W%i " R := int(reverse(K)) "; _ ^ " R ^= N "; • 0 and 1 aside (which are non-issues if the input is a positive integer), I'm confident that the code will work. I'm currently running a brute-force search for false positives. Sep 28, 2014 at 5:19 • Verfied by brute force for all unsigned 32-bit integers. Oct 2, 2014 at 17:21 # Brachylog, 4 bytes <.ṗ↔ Try it online! Simple and neat. ?<.ṗ↔. (Initial ? and final . are implicit) ?<. Input is less than the output .ṗ Output is a prime number ↔. And output reversed is the output itself (it is a palindrome) ## CJam, 18 17 characters ri{)__s_W%=*mp!}g How it works: ri "Convert the input into an integer"; { }g "Run this code block while the top stack element is truthy"; )__ "Increment the number and make two copies"; s_ "Convert one of them to string and take another copy"; W%= "Reverse the last string and compare with second last"; * "If they do not match, make the second last number 0"; mp! "Put 1 to stack if number is not prime, continuing the loop"; Try it online here ## Python, 63 60 characters def g(n): n+=1 whilen[::-1]!=nor~-2**n%n>2:n+=1 return n • This can be 2 bytes shorter as a recursive function: Try it online! – ovs Aug 21, 2018 at 13:35 ### Mathematica - 75 characters i=IntegerDigits;f@n_:=Select[Range[n+1,10^5],i@#==Reverse@i@#&&PrimeQ@#&,1] Ungolfed: i=IntegerDigits; f@n_:=Select[ Range[n+1,10^5], i@#==Reverse@i@# && PrimeQ@# &, 1 ] Sets an alias for the IntegerDigits function, then defines a function which selects the first number on the list of n+1 to 100,000 which satisfies PrimeQ and has palindromic digits. The function is called f@50000, returning {70207}. ## Haskell - 71 p n|s==reverse s&&all((/=0).mod m)[2..n]=m|1<2=p m where m=n+1;s=show m Ungolfed nextPrime n | s == reverse s && all ((/=0).(mod m)) [2..n] = m | otherwise = nextPrime (n + 1) where m = n + 1 s = show m # Pyth, 17 ~Q1WnQ_ePQ~Q1)Q Explanation: Implicit: Q = eval(input()) ~Q1 Q +=1 W while n not equal Q repr(Q) ePQ repr(end(prime_factorization(Q))) ~Q1 Q += 1 ) end while Q print(Q) # Ruby, 63 require"prime" x=->n{Prime.find{|p|q=p.to_s;p>n&&q.reverse==q}} ## Explanation • Input is taken as the arguments to a lambda. It's expected to be an Integer. • Prime is Enumerable. Use Enumerable#find to find the first prime that's bigger than the input and is equal to itself when reversed. # K (oK), 27 bytes {~(x=.|$x)&/(2_!x)!'x}(1+)/

Try it online! for all test cases where the input n<1000

My first answer in K. Yay!

Thanks to @ngn for the help.

ngn also found a shorter solution which is very wasteful. Times out on TIO for n>919.

{x+(~x=.|$x)|/x=*/!2#x}/ ### How? {~(x=.|$x)&/(2_!x)!'x}(1+)/    # Main function f, argument x
~                             # Not