/* 

  Long primes (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Long_primes
  """
  A   long prime   (as defined here)   is a prime number whose reciprocal   (in decimal)   
  has a   period length   of one less than the prime number.


  Long primes   are also known as:

                  base ten cyclic numbers
                  full reptend primes
                  golden primes
                  long period primes
                  maximal period primes
                  proper primes


  Another definition:   primes   p   such that the decimal expansion of   1/p   has period   p-1,   
  which is the greatest period possible for any integer.


  Example

  7   is the first long prime,   the reciprocal of seven is   1/7,   which is equal to the repeating decimal 
  fraction   0.142857142857···

  The length of the   repeating   part of the decimal fraction is six,   (the underlined part)   which is one 
  less than the (decimal) prime number   7.
  Thus   7   is a long prime.


  There are other (more) general definitions of a   long prime   which include wording/verbiage for bases 
  other than ten.


  Task

          Show all long primes up to   500   (preferably on one line).
          Show the   number   of long primes up to        500
          Show the   number   of long primes up to     1,000
          Show the   number   of long primes up to     2,000
          Show the   number   of long primes up to     4,000
          Show the   number   of long primes up to     8,000
          Show the   number   of long primes up to   16,000
          Show the   number   of long primes up to   32,000
          Show the   number   of long primes up to   64,000   (optional)
          Show all output here.
  """


  This program 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 =>
  println(findall(P, (member(P,primes(500)),long_prime(P)))),
  nl,
  println("Number of long primes up to limit are:"),
  foreach(Limit in [500,1_000,2_000,4_000,8_000,16_000,32_000,64_000])
     printf(" <= %5d: %4d\n", Limit, count_all( (member(P,primes(Limit)), long_prime(P)) ))
  end,
  nl.

long_prime(P) =>
  get_rep_len(P) == (P-1).

%
% Get the length of the repeating cycle for 1/n
%
get_rep_len(I) = Len => 
    FoundRemainders = {0 : _K in 1..I+1},
    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].