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


 
#lang racket
(require math/number-theory)
 
(define (truncate-right n)
  (quotient n 10))
 
(define (truncate-left n)
  (define s (number->string n))
  (string->number (substring s 1 (string-length s))))
 
(define (contains-zero? n)
  (member #\0 (string->list (number->string n))))
 
(define (truncatable? truncate n)
  (and (prime? n)
       (not (contains-zero? n))
       (or (< n 10)
           (truncatable? truncate (truncate n)))))
 
; largest left truncatable prime
(for/first ([n (in-range 1000000 1 -1)]
            #:when (truncatable? truncate-left n))
  n)
 
; largest right truncatable prime
(for/first ([n (in-range 1000000 1 -1)]
            #:when (truncatable? truncate-right n))
  n)
 
; Output:
998443
739399
 