/* 

  Euler #50 in Picat.

  Problem 50
  """
  The prime 41, can be written as the sum of six consecutive primes:
  41 = 2 + 3 + 5 + 7 + 11 + 13

  This is the longest sum of consecutive primes that adds to a prime 
  below one-hundred.

  The longest sum of consecutive primes below one-thousand that adds to a prime, 
  contains 21 terms, and is equal to 953.
  
  Which prime, below one-million, can be written as the sum of the most 
  consecutive primes?
  """


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go => time(euler50).

euler50 =>
  N = 10000,
  Primes = [P : P in 1..N, prime(P)].to_array(),
  Found = 0,
  foreach(Len in 550..-1..21, Found == 0) 
    foreach(Offset in 1..549, Found == 0)
       PP = sum([Primes[J] : J in Offset+1..Offset+Len]),
       if PP < 1000000, prime(PP) then
          Found := PP
       end
    end
  end,
  writeln(Found).

% CP approach: 0.992
euler50b =>
  N = 3950, % 10000,
  Primes = [P : P in 1..N, prime(P)],
  println([max_prime=max(Primes),sum_primes=sum(Primes)]),
  PLen = Primes.len,
  println(plen=PLen),
  X = new_list(PLen),
  X :: 0..1,

  Start :: 1..PLen,
  End :: 1..PLen,
  Start #< End,

  foreach(I in 1..PLen)
    I #< Start #=> X[I] #= 0,
    I #> End #=> X[I] #= 0,
    (I #>= Start #/\ I #<= End) #<=> X[I] #= 1
  end,

  P #= sum([X[I]*Primes[I] : I in 1..PLen]),
  P #< 1000000,
  P #> 0,
  S #= sum(X),
  S #>= 21,
  prime_cp(P),  

  Vars = X ++ [End,P,S,Start],
  solve($[ffd,down,max(S), report(printf("p:%w start:%w end:%w s:%w\n",P,Start,End,S))],Vars),
  prime(P),
  println(P).


% From lib/picat_lib_aux.pi
prime_cp(N) => 
  Ps = [2,3,5,7,11,13],
  N #> 1,  
  foreach(P in Ps)
    N mod P #> 0,  
  end,
  foreach (I in 13..2..1+sqrt(N.fd_max()))
    N mod I #!= 0
  end.

/*
prime_cp(2).
prime_cp(3).
prime_cp(5).
prime_cp(7).
prime_cp(N) :-
  N mod 2 #> 0.
prime_cp(N) :-
  N mod 3 #>0.
prime_cp(N) :-
  N mod 5 #> 0.
prime_cp(N) :-
  N mod 7 #> 0.
prime_cp(N) :-
  N #>=11,
  foreach (I in 11..2..1+sqrt(N.fd_max()))
     N mod I #> 0
  end.
*/