Shortest code to find next prime palindrome

Question

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

Answer 1

CJam, 15 bytes

li{)__mfsW%i^}g

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

Example run

$ 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                 ";

Answer 2

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)

Answer 3

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

Answer 4

Python, 63 60 characters

def g(n):
 n+=1
 while`n`[::-1]!=`n`or~-2**n%n>2:n+=1
 return n

Answer 5

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}.

Answer 6

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

Answer 7

Pyth, 17

~Q1Wn`Q_`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)

Answer 8

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.

Answer 9

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.

Answer 10

Japt, 11 bytes

_¥sÔ©Zj}aUÄ

Run it online

Answer 11

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]

Answer 12

05AB1E (legacy), 9 bytes

[>ÐÂQsp*#

Try it online or verify some test cases.

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)

Answer 13

05AB1E, 7 bytes

[ÅNDÂQ#

Try it online!

[ÅNDÂQ#  # full program
      #  # exit...
[        # infinite loop...
      #  # when...
 ÅN      # first prime greater than...
         # implicit input...
   D     # or top of stack if not first iteration...
    ÂQ   # is equal to...
 ÅN      # first prime greater than...
         # implicit input...
   D     # or top of stack if not first iteration...
    Â    # reversed
         # (implicit) exit infinite loop
   D     # implicit output

Answer 14

Raku, 37 bytes

{first &is-prime&{.flip eq$_},$_^..*}

Try it online!

The outer expression is first EXPR, $_ ^.. *, which looks for the first number which matches EXPR in the numbers from one greater than the input argument $_ to infinity. (The caret ^ in front of the .. means to exclude the starting point from the range.)

EXPR is an and-junction of two function, the built-in &is-prime and the anonymous function { .flip eq $_ }, which tests for palidrome-ness. A number matches this junction only if it matches both members.