# 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 – Optimizer Sep 27 '14 at 18:34
• Do you copy ???? – Optimizer Sep 27 '14 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. – Justin Sep 27 '14 at 19:06
• ok thanks for the clarification. I will remove the limitation of Python – Kevin Eaverquepedo Sep 27 '14 at 20:28
• yes you can assume that – Kevin Eaverquepedo Sep 28 '14 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. – Dennis Sep 28 '14 at 5:19 • Verfied by brute force for all unsigned 32-bit integers. – Dennis Oct 2 '14 at 17:21 ## 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 '18 at 13:35 # 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)  ### 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
(x=.|\$x)                     # x equals the inverse of x (is a palindrome)
&/                   # And reduction; will return truthy iff all
# results in the list are truthy (not 0)
(2_!x)             # range [2..x]
!'x          # each modulo x
{                    }(1+)/    # While loop with x+1; returns x implicitly.


# Japt, 11 bytes

_¥sÔ©Zj}aUÄ


Run it online

# JavaScript (E6) 95

Q=n=>(f=>{for(;a=!f;)for(f=++n==[...n+''].reverse().join('');b=n/++a|0,f&&a<=b;)f=a*b-n;})(0)|n


Ungolfed

Q=n=>
{
for (f=0; !f;) // loop until both palindrome and prime
{
f = ++n == [...n+''].reverse().join(''); // palindrome check
if (f) // if palindrome, check if prime
for(a = 1; b=n/++a|0, f && a<=b; )
f = a*b-n;
}
return n
}


Test In FireBFox/FireBug console

for (o=[],i=9;i<100000;)o.push(i=Q(i));console.log(o)


Output

[11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001]


# 05AB1E (legacy), 9 bytes

[>ÐÂQsp*#


Explanation:

             # (Implicit input)
#  i.e. 15
#  i.e. 130
[            # Start an infinite loop
>           #  Increase the top of the stack by 1
#   i.e. 15 + 1 → 16
#   i.e. 100 + 1 → 101
Ð          #  Triplicate that value
Â         #  Bifurcate it (short for Duplicate & Reverse)
#   i.e. 16 → 16 and '61'
#   i.e. 101 → 101 and '101'
Q        #  Check if it's equal (this checks if the number is a palindrome)
#   i.e. 16 and '61' → 0 (falsey)
#   i.e. 101 and '101' → 1 (truthy)
s       #  Swap so the value is at the top of the stack again
p      #  Check if it's a prime
#   i.e. 16 → 0 (falsey)
#   i.e. 101 → 1 (truthy)
*     #  If it's both a palindrome and a prime:
#    i.e. 0 and 0 → 0 (falsey)
#    i.e. 1 and 1 → 1 (truthy)
#    #   Stop the infinite loop
# (Implicitly outputs the resulting value)