/* 

  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.25s
euler37 =>
  % 2, 3, 5, and 7 are not considered truncable primes
  %  so we start on 9
  P = 11, 
  Sum = 0,
  C = 0,
  while (C < 11) 
     if check2(P), prime(P) then
        C := C+1,
        Sum := Sum + P
     end,
     P := P + 2
     % this is slower
     % next_prime(P,P2),  
     % P := P2
  end,
  println(Sum).


% 0.915s
euler37b =>
  % 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).


% 0.675s
euler37c =>
   println(euler37c_(11,[]).sum).

euler37c_(N,L) = L2 =>
  if L.length == 11 then
    L2 = L
  else 
    N2 = N+2,
    if is_prime3(N), check2(N) then   
      L2 = euler37c_(N2,[N|L])
    else
      L2 = euler37c_(N2,L)  
    end
  end.


% 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).