/* 

  Casting out nines problem (Rosetta Code) in Picat.

  http://rosettacode.org/wiki/Casting_out_nines
  """
  A task in three parts:

  Part 1

  Write a procedure (say co9(x)) which implements Casting Out Nines as described by 
  returning the checksum for x. Demonstrate the procedure using the examples given 
  there, or others you may consider lucky.

  Part 2

  Notwithstanding past Intel microcode errors, checking computer calculations like 
  this would not be sensible. To find a computer use for your procedure:

    - Consider the statement "318682 is 101558 + 217124 and squared is 
    101558217124" (see: Kaprekar numbers#Casting Out Nines (fast)). 
    - note that 318682 has the same checksum as (101558 + 217124); 
    - note that 101558217124 has the same checksum as (101558 + 217124) because 
      for a Kaprekar they are made up of the same digits (sometimes with extra zeroes); 
    - note that this implies that for Kaprekar numbers the checksum of k 
    equals the checksum of k2. 

  Demonstrate that your procedure can be used to generate or filter a range 
  of numbers with the property co9(k) = co9(k2) and show that this subset is a 
  small proportion of the range and contains all the Kaprekar in the range.

  Part 3

  Considering this Mathworld page, produce a efficient algorithmn based on the more 
  mathmatical treatment of Casting Out Nines, and realizing:

    co9(x) is the residual of x mod 9; 
    the procedure can be extended to bases other than 9. 

  Demonstrate your algorithm by generating or filtering a range of numbers with 
  the property k%(Base − 1) = = (k2)%(Base − 1) and show that this subset 
  is a small proportion of the range and contains all the Kaprekar in the range. 
  """

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

*/


% import util.
% import cp.


main => go.


go =>
  Base = 10,
  foreach(N in 2..6) 
     time(casting_out_nines1(Base,N))
  end,

  Base2 = 16,
  foreach(N in 2..6) 
     time(casting_out_nines1(Base2,N))
  end,
  
  nl.



casting_out_nines1(Base,N) =>
  println([base=Base,n=N]),
  C1 = 0,
  C2 = 0,
  Ks = [],
  LimitN = 3,
  foreach(K in 1..Base**N-1)
    C1 := C1 + 1,
    if K mod (Base-1) == (K*K) mod (Base-1) then
      C2 := C2+1,
      if N <= LimitN then
         Ks := Ks ++ [K]
      end
    end
  end,
  if C2 <= 100 then
    println(ks=Ks)
  end,
  printf("\nTrying %d numbers instead of %d numbers saves %2.3f%%\n", C2, C1, 100 - ((C2/C1)*100)),
  nl.