/* Euler #37 in Picat. """ 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. """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ main => go. go => time(euler37). euler37 => % 2, 3, 5, and 7 are not considered truncable primes % so we start on 9 P = 9, Sum = 0, C = 0, while (C < 11) if is_prime3(P), check(P) then C := C+1, Sum := Sum + P end, P := P + 2 end, println(Sum). % table check(N) => L = N.to_string(), Len = L.length, Tmp1 = N, foreach(I in 1..Len, is_prime3(Tmp1)) Tmp1 := [L[J] : J in I..Len].to_integer() end, is_prime3(Tmp1), L2 = L.reverse(), Tmp2 = N, foreach(I in 1..Len,is_prime3(Tmp2)) % note the reverse again. Tmp2 := reverse([L2[J] : J in I..Len]).to_integer() end, is_prime3(Tmp2). % table % prime_cached(N) => prime(N). table is_prime3(2) => true. is_prime3(3) => true. is_prime3(P) => P > 3, P mod 2 =\= 0, not has_factor3(P,3). % (improvement suggested by Neng-Fa) has_factor3(N,L), N mod L == 0 => true. has_factor3(N,L) => L * L < N, L2 = L + 2, has_factor3(N,L2).