/* 

  Project Euler #77 in Picat.
  """
  It is possible to write ten as the sum of primes in exactly five different ways:

    7 + 3
    5 + 5
    5 + 3 + 2
    3 + 3 + 2 + 2
    2 + 2 + 2 + 2 + 2

  What is the first value which can be written as the sum of primes in over five 
  thousand different ways?
  """

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

*/

% import v3_utils.
import util.
import cp.


main => go.

go ?=>
  euler77a().
go => true.
  
% 0.008s
euler77a =>
  Target = 2,
  Primes = primes(1000),
  Found = false,
  while(Found == false) 
    Ways = new_list(Target+1),
    bind_vars(Ways,0),
    Ways[1] := 1,
    foreach(I in 1..Primes.len-1)
      foreach(J in Primes[I]..Target)
        Ways[J+1] := Ways[J+1] + Ways[J-Primes[I]+1]
      end
    end,
    if last(Ways) > 5000 then
      Found := Target
    else
      Target := Target + 1
    end
  end,
  println(Found).