/* 

  The Monkey and the Coconuts problem in Picat.

  http://mathworld.wolfram.com/MonkeyandCoconutProblem.html
  """
  Given n men and a pile of coconuts, each man in sequence takes (1/n)th of the 
  coconuts left after the previous man removed his (i.e., a_1 for the first man, 
  a_2, for the second, ..., a_n for the last) and gives m coconuts 
  (specified in the problem to be the same number for each man) which do not 
  divide equally to a monkey. When all n men have so divided, they divide the 
  remaining coconuts n ways (i.e., taking an additional a coconuts each), and 
  give the m coconuts which are left over to the monkey. If m is the same at 
  each division, then how many coconuts N were there originally? 
  """
  
  Answer: The original amount of coconuts is in left[1].

  Also, see
  Gary Antonick (Wordplay at New York Times)
  "Martin Gardner’s The Monkey and the Coconuts"
  http://wordplay.blogs.nytimes.com/2013/10/07/gardner-2/
%

  Solutions for different n according to this model
   n   coconuts
   ------------
   2          7
   3         79
   4       1021
   5      15621
   6     279931
   7    5764795
   8  134217721
   9 3486784393
  
  From OEIS:
  7,79,1021,15621,279931,5764795,134217721
  http://oeis.org/A014293
  """
  A014293               n^(n+1)-n+1. 
  Solution to the classical "Monkey and Coconut Problem" 
  for n sailors.

  Also called "Sailors and Monkey Problem": a(n) is smallest 
  number such that can apply C -> (C-1)(1-1/n) n times and at 
  every step have an integer C = 1 mod n. 
  """


  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 ?=>
  N = 3, % number of men

  monkey_coconuts(N, Left,Removed),
  println(original_amount=Left[1]),  
  println(left=Left),
  println(removed=Removed),
  nl,
  
  % fail,

  nl.

go => true.

%
% Different number of men
%
go2 =>
  foreach(N in 2..10)
    monkey_coconuts(N, Left,_Removed),
    println(N=original_amount=Left[1])
  end,
  nl.


monkey_coconuts(N, Left,Removed) => 
  Left = new_list(N+1), % start at 0
  Removed = new_list(N+1),

  % I'm a little lazy figuring out the
  % full domain
  foreach(I in 1..N+1)
    Left[I] #>= 0,
    Removed[I] #>= 0
  end,

  foreach(I in 0..N-1)
    Left[I+1] #= N*Removed[I+1] + 1,
    Left[I+1+1] #= (N-1)*Removed[I+1]
  end,

  Left[N+1] #= N*Removed[N+1] + 1,

  Vars = Left ++ Removed,
  solve(Vars).