/* 

  Euler #26 in Picat.

  """
  A unit fraction contains 1 in the numerator. The decimal representation of the 
  unit fractions with denominators 2 to 10 are given:

      1/2	= 	0.5
      1/3	= 	0.(3)
      1/4	= 	0.25
      1/5	= 	0.2
      1/6	= 	0.1(6)
      1/7	= 	0.(142857)
      1/8	= 	0.125
      1/9	= 	0.(1)
      1/10	= 	0.1

  Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be 
  seen that 1/7 has a 6-digit recurring cycle.

  Find the value of d < 1000 for which 1/d contains the longest recurring cycle in 
  its decimal fraction part.
  """ 


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

*/

main => go.

go => time(euler26e). % , time(euler26b).

% 0.024s
euler26 =>
    MaxLen = 0,
    MaxD = 0,
    foreach (D in 2..999) 
      if prime(D) then
        Len = get_rep_len(D),
        if Len > MaxLen then
          MaxLen := Len,
          MaxD := D
        end
      end
    end,
    println([maxD=MaxD,maxLen=MaxLen]).

% 0.028s
euler26b =>
   M = [[get_rep_len(D),D]: D in 2..999, prime(D)].sort_down().first(),
   writeln(M).

% slighly slower than euler26/0: 0.025s
euler26c =>
  e26c(2,999,MaxD,MaxLen),
  println([d=MaxD,len=MaxLen]).

e26c(From,To,MaxD,MaxLen) =>
  e26c(From,To,0,MaxD,0,MaxLen).

e26c(From,To,MaxD0, MaxD,MaxLen0,MaxLen), From = To =>
  MaxLen = MaxLen0,
  MaxD = MaxD0.

e26c(From,To,MaxD0,MaxD,MaxLen0,MaxLen), prime(From) =>
  Len = get_rep_len(From),
  ( Len > MaxLen0 ->
      MaxLen1 = Len,
      MaxD1 = From
   ;
      MaxLen1 = MaxLen0,
      MaxD1 = MaxD0
  ),
  e26c(From+1,To,MaxD1,MaxD,MaxLen1,MaxLen).

e26c(From,To,MaxD0,MaxD,MaxLen0,MaxLen) =>
  e26c(From+1,To,MaxD0,MaxD,MaxLen0,MaxLen).


%
% This is about the same approach as euler26 etc,
% but using list comprehension.
%
% 0.025
euler26d =>
    println(sort({{get_rep_len2(N),N} : N in 11..999, prime(N)}).last.last).

%
% 0.003s And I pick this for the entry
%
euler26e =>
    println(sort({{get_rep_len3(N),N} : N in 11..999, prime(N)}).last.last).

%
% One liner: slow 4.506s
%
euler26f =>
   println([[ [ I : I in 1..N, 1==(10**I) mod N].head,N] : N in 11..999, prime(N)].max.second).

%
% Same as euler26f but using pow_mod instead
% Faster: 0.037s
%
euler26g =>
   println([[ [ I : I in 1..N, 1==pow_mod(10,I,N)].head,N] : N in 11..999, prime(N)].max.second).

%
% 1.909s
%
euler26h =>
    L = findall([X,N], (member(N,11..999),
                        prime(N),
                        get_rep_len4(N,X)
                   )),
    sort(L,1).reverse.head = [_,Max],
    println(max=Max).


%
% Get the length of the repeating cycle for 1/n.
% I.e. find the first instance where we got a repeated digit.
%
get_rep_len(I) = Len => 
    FoundRemainders = [0 : _K in 1..I+1].to_array(),
    Value = 1,
    Position = 1,
    while (FoundRemainders[Value+1] == 0, Value != 0)
        FoundRemainders[Value+1] := Position,
        Value := (Value*10) mod I,
        Position := Position+1
    end,
    Len = Position-FoundRemainders[Value+1].

%
% This works for N >= 11.
% Same idea as get_re_len/1 but using list comprehension.
% I.e. find the first position when (10**I) mod N == 1.
%
get_rep_len2(N) = {T: I in 1..N, T = pow_mod(10,I,N), break(T==1)}.length + 1.

%
% Loop version of get_rep_len2/1, i.e. skipping the list FoundRemainders
%
get_rep_len3(I) = Len =>
    Value = 1,
    Position = 1,
    Found = false,
    while (Found == false)
        Value := (Value*10) mod I,
        if Value == 1 then
           Found := Position
        else
           Position := Position+1        
        end
    end,
    Len = Position.

%
% Plain recursion
%
get_rep_len4(N,Len) :-
    get_rep_len4_(N,1,Len).
get_rep_len4_(N,I,Len) :-
    % println($get_rep_len4_(N,I,Len) ),
    (1 == 10**I mod N ->
        Len = I
     ;
        get_rep_len4_(N,I+1,Len)
    ).