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


 
;; does p include a 0 in its decimal representation ?
(define (nozero? n) (= -1 (string-index (number->string n) "0")))
 
;; right truncate : p and successive quotients by 10 (integer division) must be primes
(define (right-trunc p) (unless (zero? p) 
	(and (prime? p) (right-trunc (quotient p 10)))))
(remember 'right-trunc)
 
;; left truncate : p and successive modulo by 10, 100, .. must be prime
(define (left-trunc p (mod 1000000)) 
	(unless (< mod 1) 
	(and (prime? p) (nozero? p) (left-trunc (modulo p mod) (/ mod 10)))))
 
;; start from 999999. stop on first found
(define (fact-trunc trunc)
(for ((p (in-range 999999 100000 -1))) #:break (when (trunc p) (writeln p) #t)))
 