/* 

  Polydivisible numbers in Picat.

  What is the largest polydivisible number such that all subsequences of the number (1..n)
  is divisible by n?

  See the Picat forum for a discussion:
  https://groups.google.com/forum/#!topic/picat-lang/Cb3RWZ6h-LE

  Note that the cp/sat modules can only use integers <= 2*56 (i.e. max 17 digit numbers) so
  we have to use Picat's arbitrary precision and backtrack features.


  Number of polydivisible numbers of a certain length (see go3/0):
   N  #solutions
   -----------
   1 = 9
   2 = 45
   3 = 150
   4 = 375
   5 = 750
   6 = 1200
   7 = 1713
   8 = 2227
   9 = 2492
   10 = 2492
   11 = 2225
   12 = 2041
   13 = 1575
   14 = 1132
   15 = 770
   16 = 571
   17 = 335
   18 = 180
   19 = 90
   20 = 44
   21 = 18
   22 = 12
   23 = 6
   24 = 3
   25 = 1
   26 = 0

  The main tests:
  * go: test N=25
  * go2: all solutions for N=10
  * go3: number of solutions for 1..26 (the table above)
  * go4: there is no length 26 polydivisible number

  Also see:
  * https://en.wikipedia.org/wiki/Polydivisible_number
  * http://www.blog.republicofmath.com/the-number-3608528850368400786036725/

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

*/


import util.

main => go.

%
% Find the polydivisible number of length 25
%
go ?=> 
  N = 25,
  div1_n(N, _X, Int),
  println(Int),
  println(check),
  check(Int),
  nl.

go => 
  println("Sorry, but there is no solution!").


%
% find all polydivisible number of a certain length
%
go2 => 
  N = 10,
  println(n=N),
  All = findall(Int, div1_n(N,_X,Int)),
  foreach(A in All)
    println(A),
    check(A),
    nl
  end,
  println(number_of_solutions=All.len),
  nl.


% find how many polydivisible numbers there are of a certain length
go3 => 
  foreach(N in 1..26)
     All = findall(Int, div1_n(N,_X,Int)),
     println(N=All.len)
  end,
  nl.


% There is no polydivisible number of length 26
go4 ?=> 
  N = 26,
  div1_n(N, X, Int),
  println(x=X),
  println(Int),
  println(check),
  check(Int),
  nl.

go4 => 
  println("Sorry, but there is no solution!").


%
% check that N really is a polydivisible number
%
check(N) => 
  X = N.to_string(),
  Len = X.len,
  foreach(I in 1..Len)
     L = [X[K].to_string() : K in 1..I],
     Int = L.join('').to_integer(),
     Mod = Int mod I,
     printf("%w mod %w == %w\n", Int, I, Mod),
     if Mod != 0 then
       printf("Sorry, but %w does not divide the number!\n", I)
     end
  end,
  nl.
 
% 
% create a polydivisible number of length N
%
div1_n(N, X, Int2) => 
  X = new_list(N),
  Int = 0,
  foreach(I in 1..N)
     F = false,
     member(J, 0..9), % try a digit
     X[I] := J,
     L = [X[K].to_string() : K in 1..I],
     Int := L.join('').to_integer(),
     if Int > 0, Int mod I == 0 then
        F := true
     end,
     if F == false then 
       fail 
     end
  end,
  Int2 = Int.