A truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number.



Examples

The number 997 is called a left-truncatable prime as the numbers 997, 97, and 7 are all prime.

The number 7393 is a right-truncatable prime as the numbers 7393, 739, 73, and 7 formed by removing digits from its right are also prime.

No zeroes are allowed in truncatable primes.



Task

The task is to find the largest left-truncatable and right-truncatable primes less than one million (base 10 is implied).



Related tasks
 
 Find largest left truncatable prime in a given base
 Sieve of Eratosthenes


See also

 Truncatable Prime from MathWorld.]


def left_truncatable?(n)
  truncatable?(n) {|i| i.to_s[1..-1].to_i}
end
 
 
def right_truncatable?(n)
  truncatable?(n) {|i| i/10}
end
 
def truncatable?(n, &trunc_func)
  return false if n.to_s.include? "0"
  loop do
    n = trunc_func.call(n)
    return true if n.zero?
    return false unless Prime.prime?(n)
  end
end
 
require 'prime'
primes = Prime.each(1_000_000).to_a.reverse
 
p primes.detect {|p| left_truncatable? p}
p primes.detect {|p| right_truncatable? p}