The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.


import Data.List
sieve (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=).(`mod` p)) qs'))
where (ps',qs') = span (<p*p) qs
primes = iterate sieve([2],([3],[3,5..]))>>=fst
prime n = takeWhile(<10^n).dropWhile(<10^(n-1))$ primes
left 1 = [2,3,5,7]
left (n+1) = [read.(m:)$show t|m<-"123456789",t<-left n]`intersect` prime (n+1)
right 1 = [2,3,5,7]
right (n+1) =[read$show t ++[m]|m<-"1379",t<-right n ]`intersect` prime (n+1)
trunc n = left n`intersect`right n
p037 =sum.take 11$concatMap trunc [2..]
main = print p037