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


# You could have symmetric algorithms for max right and left
# truncatable numbers, but they lend themselves to slightly
# different optimizations.
 
max_right_truncatable_number = (n, f) ->
  # This algorithm only evaluates 37 numbers for primeness to
  # get the max right truncatable prime < 1000000.  Its
  # optimization is that it prunes candidates for
  # the first n-1 digits before having to iterate through
  # the 10 possibilities for the last digit.
  if n < 10
    candidate = n 
    while candidate > 0
      return candidate if f(candidate)
      candidate -= 1
  else
    left = Math.floor n / 10
    while left > 0
      left = max_right_truncatable_number left, f
      right = 9
      while right > 0
        candidate = left * 10 + right
        return candidate if candidate <= n and f(candidate)
        right -= 1
      left -= 1
  throw Error "none found"
 
max_left_truncatable_number = (max, f) ->
  # This is a pretty straightforward countdown.  The first
  # optimization here would probably be to cache results of 
  # calling f on small numbers.
  is_left_truncatable = (n) ->
    candidate = 0
    power_of_ten = 1
    while n > 0
      r = n  % 10
      return false if r == 0
      n = Math.floor n / 10
      candidate = r * power_of_ten + candidate
      power_of_ten *= 10
      return false unless f(candidate)
    true
  do ->
    n = max
    while n > 0
      return n if is_left_truncatable n, f
      n -= 1
    throw Error "none found"
 
is_prime = (n) ->
  return false if n == 1
  return true if n == 2
  for d in [2..n]
    return false if n % d == 0
    return true if d * d >= n
 
 
console.log "right", max_right_truncatable_number(999999, is_prime)
console.log "left", max_left_truncatable_number(999999, is_prime)
 