/*
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).
% 0.915s
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), check2(P) then
C := C+1,
Sum := Sum + P
end,
P := P + 2
% this is slower
% next_prime(P,P2),
% P := P2
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).
%
% this is slightly faster than check/1
%
% table
check2(N) =>
OK = 1,
foreach(I in 1..nlen(N)-1, OK == 1)
II = 10**I,
if not is_prime3(N mod II); not is_prime3(N div II) then
OK := 0
end
end,
OK == 1.
% table
check3(N) =>
NLen1 = nlen(N)-1,
NLen1 = [1 : I in 1..NLen1, II = 10**I, is_prime3(N mod II), is_prime3(N div II)].length.
nlen(N) = floor(log10(N))+1.
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).
% next prime
next_prime(Num, P) => Num2 = Num + 1, next_prime2(Num2, P).
next_prime2(Num, P) ?=> is_prime3(Num), P = Num.
next_prime2(Num, P) =>
Num2 = Num+1,
next_prime2(Num2,P).