7
\$\begingroup\$

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
\$\endgroup\$
  • 7
    \$\begingroup\$ 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 \$\endgroup\$ – Optimizer Sep 27 '14 at 18:34
  • \$\begingroup\$ Do you copy ???? \$\endgroup\$ – Optimizer Sep 27 '14 at 18:43
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Justin Sep 27 '14 at 19:06
  • \$\begingroup\$ ok thanks for the clarification. I will remove the limitation of Python \$\endgroup\$ – Kevin Eaverquepedo Sep 27 '14 at 20:28
  • 1
    \$\begingroup\$ yes you can assume that \$\endgroup\$ – Kevin Eaverquepedo Sep 28 '14 at 8:49

12 Answers 12

6
\$\begingroup\$

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                 ";
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Sep 28 '14 at 5:19
  • \$\begingroup\$ Verfied by brute force for all unsigned 32-bit integers. \$\endgroup\$ – Dennis Oct 2 '14 at 17:21
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

Python, 63 60 characters

def g(n):
 n+=1
 while`n`[::-1]!=`n`or~-2**n%n>2:n+=1
 return n
\$\endgroup\$
  • 1
    \$\begingroup\$ This can be 2 bytes shorter as a recursive function: Try it online! \$\endgroup\$ – ovs Aug 21 '18 at 13:35
4
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

Japt, 11 bytes

_¥sÔ©Zj}aUÄ

Run it online

\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.