/*
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).